백준14502 - 연구소

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

bfs를 이용하여 풀었다. 푸는 방법은 벽을 우선 세 개를 세운뒤에 바이러스가 퍼지게 만들고 바이러스가 펴지지 않은 공간을 카운팅하여 바이러스가 퍼지지 않은 최대 공간의 갯수를 구하면 되었다. 

 

우선 벽을 세우기 위하여 3중 for문을 사용하였다. 이미 벽이거나 바이러스가 있는 공간이면 건너뛰었다. 이런식으로 총 세 개의 공간에 벽을 세웠다.

 

벽을 세 개 세웠으면 bfs를 이용하여 바이러스를 현재 바이러스가 있는 곳을 기점으로 상하좌우로 퍼뜨렸다. 

 

이런식으로 하면 최종적으로 바이러스가 퍼진 공간의 정보가 나오기 때문에 바이러스가 퍼지지 않은 공간을 알 수 있다.

 

#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
#define MAX 9
using namespace std;

int N, M; //좌표 크기
int mat[MAX][MAX]; //맵의 정보
int temp[MAX][MAX]; //bfs()를 사용할 때 탐색할 공간
int ans = -1; //바이러스가 퍼지지 않은 최대 공간
int cnt = 0; //각각의 케이스마다 바이러스가 퍼지지 않은 공간

//상하좌우
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

bool visit[MAX][MAX]; //방문 여부

queue<pair<int, int>> q; //bfs 이용시 바이러스가 있는 곳을 담아둘 변수
queue<pair<int, int >> start; //처음 바이러스가 있는 시작

void bfs() {
	q = start;
	while (!q.empty()) {
		//첫번째 좌표를 추출하여 방문 처리하고 삭제한다.
		int x = q.front().first;
		int y = q.front().second;
		visit[x][y] = true;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			//좌표 범위 안에서 유효하고 방문하지 않은 공간이면 빈 공간일 경우 바이러스를 옮기고 그 공간을 큐에 삽입한다.
			if (1 <= nx && nx <= N && 1 <= ny && ny <= M && !visit[nx][ny] && temp[nx][ny] == 0) {
				temp[nx][ny] = 2;
				q.push(pair<int, int>(nx, ny));
			}
		}
	}
}

void solve() {
	//3중 포문을 이용하여 벽을 세운다.
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			//이미 무언가가 있으면 넘어가고 길이면 1로 채운다.
			if (mat[i][j] != 0) {
				continue;
			}
			else {
				mat[i][j] = 1;
			}
			for (int k = 1; k <= N; k++) {
				for (int l = 1; l <= M; l++) {
					//이미 무언가가 있으면 넘어가고 길이면 1로 채운다.
					if (mat[k][l] != 0) {
						continue;
					}
					else {
						mat[k][l] = 1;
					}
					for (int m = 1; m <= N; m++) {
						for (int n = 1; n <= M; n++) {
							//이미 무언가가 있으면 넘어가고 길이면 1로 채운다.
							if (mat[m][n] != 0) {
								continue;
							}
							else {
								cnt = 0; //처음에 각각의 바이러스가 없는 공간의 변수를 0으로 초기화
								mat[m][n] = 1;

								//bfs를 위하여 좌표 공간을 벽이 3개 세워진 공간으로 초기화하고 모든 곳을 미방문처리
								for (int a = 1; a <= N; a++) {
									for (int b = 1; b <= M; b++) {
										temp[a][b] = mat[a][b];
										visit[a][b] = false;
									}
								}

								bfs(); //탐색
								
								//바이러스가 퍼지지 않은 곳을 찾는다.
								for (int a = 1; a <= N; a++) {
									for (int b = 1; b <= M; b++) {
										if (temp[a][b] == 0) {
											cnt++;
										}
									}
								}

								ans = max(ans, cnt); //최대 경우의 수를 찾는다.
							}
							mat[m][n] = 0; //벽이 었던 공간을 0으로 다시 돌려서 처음 입력한 상태로 돌린다.
						}
					}
					mat[k][l] = 0; //벽이 었던 공간을 0으로 다시 돌려서 처음 입력한 상태로 돌린다.
				}
			}
			mat[i][j] = 0; //벽이 었던 공간을 0으로 다시 돌려서 처음 입력한 상태로 돌린다.
		}
	}
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> mat[i][j];
			if (mat[i][j] == 2) {
				start.push(pair<int, int>(i, j));
			}
		}
	}

	solve();

	cout << ans;
}