[C++][백준] 14502번 연구소 :: seoftware

---

 

소스코드

---

BFS, 브루트포스

#include <iostream>
#include <queue>
using namespace std;
int N, M;
int map[8][8];
int temp[8][8];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
int answer = 0;
//temp에 기존 map을 복사하는 함수
void copyMap(int (*from)[8], int (*to)[8]) {
	for (int n = 0; n < N; n++) {
		for (int m = 0; m < M; m++) {
			to[n][m] = from[n][m];
		}
	}
}
//[BFS] 벽을 3개 세운 후 바이러스를 퍼뜨리고 전염되지 않은 곳을 세준다.
void spreadVirus() {
	int result[8][8];
	copyMap(temp, result);
    //바이러스가 있는 곳(2)의 사방을 전염시킨다.
	queue<pair<int, int>> q;
	for (int n = 0; n < N; n++) {
		for (int m = 0; m < M; m++) {
			if (result[n][m] == 2) {
				q.push({ n, m });
			}
		}
	}
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
				if (result[nx][ny] == 0) {
					result[nx][ny] = 2;
					q.push({ nx, ny });
				}
			}
		}
	}
    //바이러스가 전염되지 않은 곳(0)을 세어준다.
	int noVirus = 0;
	for (int n = 0; n < N; n++) {
		for (int m = 0; m < M; m++) {
			if (result[n][m] == 0) noVirus++;
		}
	}
	if (noVirus > answer) answer = noVirus;
}
//[브루트포스] 가능한 모든 경우의 수로 벽을 3개 세운다.
void buildWall(int cnt) {
	if (cnt == 3) {
		spreadVirus();
		return;
	}
	for (int n = 0; n < N; n++) {
		for (int m = 0; m < M; m++) {
			if (temp[n][m] == 0) {
				temp[n][m] = 1; //벽세우기
				buildWall(cnt+1); //벽 세운 횟수를 +1
				temp[n][m] = 0; //기존의 상태로 돌아가기(벽허물기)
			}
		}
	}
}
int main(void) {
	//input
	scanf("%d %d", &N, &M);
	for (int n = 0; n < N; n++) {
		for (int m = 0; m < M; m++) {
			scanf("%d", &map[n][m]);
		}
	}
    //perform
	for (int n = 0; n < N; n++) {
		for (int m = 0; m < M; m++) {
			if (map[n][m] == 0) {
				copyMap(map, temp);
				temp[n][m] = 1; // 벽세우기
				buildWall(1); //벽 하나 세웠으므로 cnt = 1
				temp[n][m] = 0; //벽허물기(원래 상태로 돌아가기)
			}
		}
	}
    //output
	printf("%d\n", answer);
}

1. map을 temp에 복사한다.

2. (buildWall) temp에서 0인 지점 3개를 1로 만든다(모든 경우의 수로).

3. (spreadVirus) 벽에 3개 지어지면 bfs를 이용하여 바이러스를 퍼뜨린다. 2의 상하좌우를 확인하여 0이면 퍼뜨린다.

4. (spreadVirus) 3번 과정이 남은 후 바이러스가 전염되지 않은 구간(0)이 몇 개인지 세어준다.