백준 14502 : 연구소

문제 접근

---

일단은 구현부터 해보자고 생각했다. 완전탐색으로 3 군데에 0을 1로 바꿔 놓은 뒤, 2 위치 좌표 기억해뒀다가 DFS 로 안전 구역 크기를 계산하게 구현하고자 했다. 0 개수를 count 했다가 DFS 에서 0 만나면 -1 하도록 했다.

 

일단 수도 코드 간략하게 작성해보고, 시간 복잡도 계산해보니까 N,M 이 8 이하이므로 완전 탐색하는 경우는 최악의 경우 64C3 이었고, DFS 의 경우 map 크기 + map 크기 였다. ( V+E 인데 이웃과 다 연결되어있다고 생각하므로 ) 따라서 64C3 * (64+64) 였고, 계산해보니 5,332,992 가 나와 충분히 가능할 거라고 생각했다. 시간 복잡도는 O((N*M)^4) 이지만 N, M 의 입력 범위가 적어 가능했다.

 

주의할 것!

1. 전역 변수에 선언한 걸 깜빡하고, 지역 변수에 다시 선언하지 말자. 치명적인 오류가 생길 수 있다.
2. 반복문 조건 잘 확인하자.

 

문제 코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// visited : 해당 좌표를 방문했는지 확인. -> 이 덕분에 map 을 다시 만들 필요 없음.
// tmp : dfs() 안에서 임시적으로 쓰이는 안전 구역의 넓이.
bool visited[11][11];
int map[11][11];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int N, M, tmp, ans=0;

// virus : 바이러스(2)가 있는 좌표를 저장한 벡터.
// hollow : 빈 공간(0)이 있는 좌표를 저장한 벡터.
vector<pair<int, int>> virus, hollow;

// 브루트포스가 잘 되고 있는지 확인하기 위한 print 함수. ( 겉 테두리까지 같이 출력 )
void print()
{
	cout<<"\n====="<<tmp<<"=====\n";
	for(int j=0; j<N+2; ++j)
	{
		for(int i=0; i<M+2; ++i)
			cout<<map[i][j]<<' ';
		cout<<'\n';
	}
}

// 바이러스 주변을 잠식하는 과정을 담당하는 dfs 함수.
// 호출한 좌표를 방문처리 한 뒤 상하좌우 검사 후 방문하지 않은 0이 있다면 해당 영역 감염으로 판단.
// --tmp 를 해준 뒤 방문하지 않은 0의 좌표 주변을 검사하기 위해 dfs(해당 좌표) 호출.
void dfs(int x, int y)
{
	visited[x][y] = true;
	
	for(int j=0; j<4; ++j)
		if(!visited[x+dx[j]][y+dy[j]] && map[x+dx[j]][y+dy[j]] == 0)
		{
			--tmp;
			dfs(x+dx[j], y+dy[j]);
		}
}

int main(void)
{
	fill(&map[0][0], &map[10][10], 1);
	cin>>N>>M;
	
	for(int j=1; j<=N; ++j)
		for(int i=1; i<=M; ++i)
		{
			cin>>map[i][j];
			
			if(map[i][j]==0)
				hollow.push_back(make_pair(i,j));
			
			else if(map[i][j]==2)
				virus.push_back(make_pair(i,j));
		}
	
    // 브루트포스 코드, 새로 세울 각 벽에 다른 번호를 넣어서 전부 잘 들어가고 있는지 확인.
	for(int i=0; i<hollow.size()-2; ++i)
	{
		map[hollow[i].first][hollow[i].second] = 7;
		for(int j=i+1; j<hollow.size()-1; ++j)
		{
			map[hollow[j].first][hollow[j].second] = 8;
			for(int k=j+1; k<hollow.size(); ++k)
			{
				map[hollow[k].first][hollow[k].second] = 9;
				
                // 벽 3개를 세웠으니 3을 감소한다.
                // 전 시도에서 visited 가 사용되었으니 초기화.
				tmp = hollow.size()-3;
				fill(&visited[0][0], &visited[10][10], false);
				
				for(int l=0; l<virus.size(); ++l)
					dfs(virus[l].first, virus[l].second);
			
				ans = max(ans,tmp);
				//if(ans == tmp)
				//	print();
				
				map[hollow[k].first][hollow[k].second] = 0;
			}
			map[hollow[j].first][hollow[j].second] = 0;
		}
		map[hollow[i].first][hollow[i].second] = 0;
	}
	
	cout<<ans<<'\n';
}