[백준] 14502번 연구소 (C++, 삼성 기출)

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

이 문제는 완전 탐색 + bfs로 해결했다.
가로, 세로의 최대 크기가 8이므로 완전 탐색으로 풀이가 가능하다.

1. 완전 탐색으로 벽을 3개 세울 수 있는 가능한 모든 경우를 구해준다.
2. 모든 경우에서 bfs로 바이러스를 퍼트린 뒤, 안전 영역을 세어준다.

#include <iostream>
#include <queue>

using namespace std;

int n, m;
int map[9][9];
int dir[4][2] = { {1,0}, {-1,0}, {0,1},{0,-1} };
int ans = 0;

void bfs() {
	queue<pair<int, int>> q;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (map[i][j] == 2)
				q.push({ j, i });
	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 + dir[i][0];
			int ny = y + dir[i][1];
			if (nx <0 || nx >= m || ny <0 || ny >= n) continue;
			if (map[ny][nx] == 0) {
				map[ny][nx] = 2;
				q.push({ nx, ny });
			}
		}
	}
	int sum = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (map[i][j] == 0){
				sum++;
			}
	ans = max(ans, sum);
}

void solve(int x, int y, int depth) {
	if (depth == 3) {
		int cp[9][9];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				cp[i][j] = map[i][j];
		bfs();
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				map[i][j] = cp[i][j];
		return;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0) {
				map[i][j] = 1;
				solve(j, i, depth + 1);
				map[i][j] = 0;
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];
	solve(0, 0, 0);
	cout << ans;
}