[bfs] [연결 요소] 바이러스 14502 (재)

문제 해설 및 주의사항

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

 

---

 

풀이

1. 문제의 구분

 

- 벽을 3개 세우는 것 (브루트 포스) 

시간 복잡도 : (NM)^3

 

- 바이러스가 퍼질 수 없는 영역의 크기 구하기 (연결 요소의 개수)

바이러스가 있는 곳을 기준으로, 바이러스가 퍼질 영역을 dfs 혹은 bfs 로 구한 뒤, 여집합을 구하면 된다.

시간 복잡도 : (NM)

 

그러므로, 최대 경우의 수는 (8 * 8)^4 . 충분하다.

 

2. 문제 풀이

- 주석 참조

 

 

---

풀이코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
// 연구소 14502

int n, m;
// 연구소 맵
int board[10][10];
// 바이러스를 모두 전파한 맵
int virused[10][10];

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int bfs(){
	int ret = 0;
	
	queue<pair<int, int>> q;
	
	// 맵을 복사한다.
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			virused[i][j] = board[i][j];
			// bfs 시작 처리
			// 감염지역이라면, 시작점으로써, q에 넣는다.
			if(virused[i][j] == 2){
				q.push(make_pair(i,j));
			}
		}
	}
	
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int k = 0; k < 4; k++){
			int nx = x + dx[k];
			int ny = y + dy[k];
			
			// 범위 체크
			if(0 <= nx && nx < n && 0 <= ny && ny < m){
				// 다음 칸이 빈칸이라면, 바이러스를 전파한다.
				if(virused[nx][ny] == 0){
					virused[nx][ny] = 2;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}
	
	for(int i = 0 ; i < n ; i++){
		for(int j = 0; j < m; j++){
			if(virused[i][j] == 0){
				ret += 1;
			}
		}
	}
	return ret;
}


int main(){
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> board[i][j];
		}
	}
	
	int ans = 0;
	// 첫번째 벽을 놓을 좌표
	for(int x1 = 0; x1 < n; x1++){
		for(int y1 = 0; y1 < m; y1++){
			// 빈 칸이 아니라면 생략
			if(board[x1][y1] != 0) continue;
				// 두번째 벽
				for(int x2 = 0; x2 < n; x2++){
					for(int y2 = 0; y2 < m; y2++){
						// 빈 칸이 아니라면 생략
						if(board[x2][y2] != 0) continue;
						// 세번째 벽
						for(int x3 = 0; x3 < n; x3++){
							for(int y3 = 0; y3 < m; y3++){
								// 빈 칸이 아니라면 생략
								if(board[x3][y3] != 0) continue;
								
								// 세 벽 중 일치하는 좌표가 있으면 생략
								if (x1 == x2 && y1 == y2) continue;
								if (x1 == x3 && y1 == y3) continue;
								if (x2 == x3 && y2 == y3) continue;
								
								// 벽을 놓는다.
								board[x1][y1] = 1;
								board[x2][y2] = 1;
								board[x3][y3] = 1;
								
								// 현재 놓은 벽 상황에서, 최소 감염 구역 구한다.
								int current_ans = bfs();
								if(ans < current_ans) ans = current_ans;
								
								// 벽을 다시 없앤다.
								board[x1][y1] = 0;
								board[x2][y2] = 0;
								board[x3][y3] = 0;
							}
						}
					}
				}
		}
	}
	printf("%d\n", ans);
	
}

 

---

퇴고

1. 문제를 분석하는 능력.

- 벽을 3개 세우는 것 과 바이러스 안전 영역을 구하는 것. 이렇게 문제를 2개로 나누어 보았다면 바로 풀이가 떠올랐을 것이다. 합친 문제는 처음 보는 문제이지만, 나눈 문제는 이전에 보았던 문제들과 다를 것이 없었기 때문이다.

 

2. 브루트 포스

- 브루트 포스는 재귀로만 하는 것이 아니다. 벽 3개를 놓는 상황을 재귀로 구현해내는 건 어렵다. 그 대신 벽 1개당 2개 for 문 즉, 6중 for 문으로 브루트 포스를 할 수 있다. 브루트 포스 = 재귀 라는 고정관념은 없애자.

 

브루트 포스에서 어떠한 것을 N 개 ~~ 해라 라고 하였을 때, N 이 고정된 값이라면 for 문을 사용하는 것이 훨씬 낫다.

 

3. 연결 요소의 개수 세기

- 이전에 연결 요소의 개수를 세려면, 모든 시작점에서 각각 bfs / dfs 를 실시해주었다. 왜냐면, 각 연결 요소의 크기를 알아내야 했기 때문이다. 이 문제에서는 달랐다. 연결 요소의 개수를 모두 더한 것이 답이기 때문에, 연결 요소의 각 시작점들 (바이러스 첫 감염지) 를 queue 에 넣고 bfs 를 돌리면 되었다.