[C++][백준] - 연구소 (14502번)

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

14502번: 연구소

🔔 문제 : 

(3<= N, M <= 8) 인 N*M 크기의 연구소가 있습니다.

 

이 연구소에는 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳입니다.

 

아무런 벽을 3개를 세워서 바이러스가 감염시키는 방을 최소한으로 줄여야합니다.

 

즉 빈 방 0이 살아남는것을 최대한으로 해야합니다. 

 

얻을 수 있는 0의 영역의 최대 크기를 출력하면 되는 문제입니다.

 

요렇게 생긴 연구소에서

 

벽을 3개 가져다가 이렇게 막아버리면 바이러스는

 

요렇게 퍼집니다.

 

 

 

단, 바이러스는 좌우 위아래로만 퍼트려질 수 있습니다.

---

🔔 Kick Point :

저는 우선, 연구소가 최대값이 8 * 8 크기이지만, 그 테두리에  벽인 1을 추가하여 패딩을 주었습니다.

따라서 map[10][10] 크기로 두고 진행하였습니다.

 

이후 빈 방인지 바이러스인지 벽인지 입력값을 받고나서, 테두리를 벽으로 막아버렸습니다.

 

그다음에는 BFS() 를 통하여 바이러스가 자연스레 퍼지도록 함수를 만들고

 

DFS()의 Combination을 통하여 벽을 세우는 모든 경우의 수를 두어서, 

 

Cal() 을 통하여 진행을 시키고, 남은 빈방의 값을 구하였습니다.

 

 

BFS() 기능 // 바이러스 퍼트리기

 

바이러스를 퍼트리는 실험으로 퍼트려진 곳은 3으로 두고

끝난 후 퍼트린 곳은 다시 0인 빈방으로 돌리고 다시 벽을 세울 수 있게 해줍니다.

---

🔔 Code :

#include <iostream>
#include <queue>
using namespace std;

int n, m;
int map[10][10];
int MAX = 0;
queue<pair<int, int>> q;

// 조합 + BFS
// 바이러스 퍼트리기
void BFS(int x, int y) {
	q.push({ x,y });

	while (!q.empty()) {
		int _x = q.front().first;
		int _y = q.front().second;
		q.pop();

		if (map[_x + 1][_y] == 0) {
			q.push({ _x + 1,_y }); 
			map[_x + 1][_y] = 3;
		}
		if (map[_x][_y + 1] == 0) {
			q.push({ _x,_y +1});
			map[_x][_y + 1] = 3;
		}
		if (map[_x - 1][_y] == 0) {
			q.push({ _x - 1,_y });
			map[_x - 1][_y] = 3;
		}
		if (map[_x][_y - 1] == 0) {
			q.push({ _x ,_y - 1});
			map[_x ][_y - 1] = 3;
		}
	}
}

int Cal() {
	for (int i = 0; i < n * m; i++) {
		int x = i / m;
		int y = i % m;
		x++, y++;
		if (map[x][y] == 2) BFS(x, y);
	}

	int _cnt = 0;
	
	for (int i = 0; i < n * m; i++) {
		int x = i / m;
		int y = i % m;
		x++, y++;
		if (map[x][y] == 0) _cnt++;
		if (map[x][y] == 3) map[x][y] = 0;
	}
	
	return _cnt;
}


// 벽세우기
void DFS(int cnt = 0, int k =0) {
	if (cnt == 3) {

		int tmp = Cal();
		MAX = MAX < tmp ? tmp : MAX;
		return;
	}
	else {
		for (int i = k; i < (n * m); i++) {
			int x = i / m;
			int y = i % m;
			x++, y++;
			
			if (map[x][y] == 0) {
				map[x][y] = 1;
				DFS(cnt+ 1, i + 1);
				map[x][y] = 0;
			}
		}
	}
}


int main() {

	cin >> n >> m;

	// INPUT
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> map[i][j];
		}
	}

	// 주위 벽치기
	for (int i = 0; i <= m + 1; i++) {
		map[0][i] = 1;
		map[n + 1][i] = 1;
	}
	for (int i = 0; i <= n + 1; i++) {
		map[i][0] = 1;
		map[i][m+1] = 1;
	}
	
	DFS();
	cout << MAX;
}

---