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

 

 

 

BFS와 Brute force를 섞어야하는 문제였다.

Brute force를 공부하기 전이라 관련 포스팅을 참고 하였다. 

 

연구소에 세개의 벽을 세운후 퍼진 바이러스의 영향을 받지 않은 영역의 수의 최댓값을 구하는 문제다.

내 기준 굉장히 까다로운 문제였다..

 

1. 벽과 바이러스가 없는 0인 자리에 벽 3개를 세웠을 때의 모든 경우의 수를 따져야한다. ---> brute force
2. 연구소 상태를 복사하여 테스트 할 이차원배열이 따로 필요하다
3. 바이러스가 퍼진 후의 연구실 상태를 구하고 그 후, 그때의 0인 자리 수를 세야한다. ---> bfs
4. 처음에 예시를 제대로 보지 않아 헷갈렸던 것  ---> 2의 바로 옆에만 벽을 세우는 게 아니다!!! (그래서 brute force)
5. 벽을 3개 세워 볼 때마다 나오는 0인 자리 개수는 max로 그때 그때 비교해서 result로 세팅한다.
6. 모든 경우의 수가 끝나고 나온 result 값이 0의 자리의 최댓값이 된다.

 

 

 

#include <iostream>
#include <queue>
//#include <cstring> //memset
#include <algorithm>
using namespace std;

const int MAX = 8;

typedef struct
{
	int y, x;
}Dir;

Dir moveDir[4] = { { 0, 1 },{ 0, -1 },{ 1, 0 },{ -1, 0 } };


int N, M;
int lab[MAX][MAX];
int temp[MAX][MAX];	// brute force를 위해 연구실 상태를 복사할 곳
int result;

// 벽을 세운후 바이러스가 퍼진 연구실 상태를 구해서 안전한 영역을 센다
void BFS(void) {

	int afterSpread[MAX][MAX];

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			afterSpread[i][j] = temp[i][j];
		}
	}

	queue<pair<int, int>> q;	// y, x
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (afterSpread[i][j] == 2)		// 바이러스라면
				q.push(make_pair(i, j));	//큐에 넣는다
		}
	}

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = y + moveDir[i].y;
			int nextX = x + moveDir[i].x;

			if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M) {
				if (afterSpread[nextY][nextX] == 0)	//빈칸이라면
				{
					afterSpread[nextY][nextX] = 2;	//바이러스 감염

					q.push(make_pair(nextY, nextX));
				}
			}
		}
	}

	int empty = 0;

	// 안전한 영역 세기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (afterSpread[i][j] == 0)
				empty++;
		}
	}

	result = max(result, empty);	// 전 것과 비교해 더 큰 걸 result로 함
}


//무작위로 벽을 3개 세우는 함수
void makeWall(int cnt) {

	if (cnt == 3)	//벽을 세개 만들었으므로
	{
		BFS();	//안전영역 개수 세기
		return;
	}

	//나머지 벽 두개를 세운다
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (temp[i][j] == 0) {
				temp[i][j] = 1;	//마찬가지로 해당칸에 세우고
				makeWall(cnt + 1);
				temp[i][j] = 0;	//다시 허문다
			}
		}
	}
}


int main(void) {
	
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> lab[i][j];
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (lab[i][j] == 0) {	//빈칸 발견 시
				
				//연구실 상태를 복사한다
				for (int k = 0; k < N; k++) {
					for (int l = 0; l < M; l++) {
						temp[k][l] = lab[k][l];
					}
				}

				temp[i][j] = 1;	//해당 칸에 벽을 세운다
				makeWall(1);	//벽을 세운 상태이므로 cnt = 1
				temp[i][j] = 0;	//다시 허문다

			}
		}
	}

	cout << result << endl;

	return 0;
}