[C++]BOJ 14502 - 연구소

주어진 지도의 크기가 최대 8 * 8이므로 바이러스와 벽이 아무것도 없다고 가정하면 벽을 세울 수 있는 경우의 수는 64C3 대략, 40,000 가지이다.
그러므로 벽을 세우는 문제는 완전탐색으로 해결할 수 있다.
벽을 세우는 모든 방법의 수 마다 바이러스가 퍼지는 경우를 dfs로 탐색하고 안전영역이 가장 큰 경우의 수를 기억해 마지막에 전체 칸의 갯수 - 퍼진 바이러스의 갯수 - 처음에 있던 벽의 갯수 - 3을 출력한다.

bfs로도 풀 수 있다. 귀찮아서 안 해봤다.

#include <iostream>
#include <cstring>
using namespace std;
int n, m, arr[10][10], v[10][10], ay, ax, by, bx, cy, cx, tmp, dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0}, tx, ty, wal, vir = 1e9;
void dfs(int x, int y) {
	v[y][x] = 1; tmp++;
	for(int i = 0; i < 4; i++) {
		tx = x + dx[i]; ty = y + dy[i];
		if(tx > m || ty > n || tx < 1 || ty < 1 || v[ty][tx] || arr[ty][tx]) continue;
		dfs(tx, ty);
	}
}
int solve() {
	memset(v, 0, sizeof(v)); tmp = 0;
	arr[ay][ax] = 1; arr[by][bx] = 1; arr[cy][cx] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(arr[i][j] == 2) dfs(j, i);
	arr[ay][ax] = 0; arr[by][bx] = 0; arr[cy][cx] = 0;
	return tmp;
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			if(arr[i][j] == 1) wal++;
		}
	for(ay = 1; ay <= n; ay++)
		for(ax = 1; ax <= m; ax++) {
			if(arr[ay][ax]) continue;
			for(by = 1; by <= n; by++)
				for(bx = 1; bx <= m; bx++) {
					if(arr[by][bx]) continue;
					for(cy = 1; cy <= n; cy++)
						for(cx = 1; cx <= m; cx++) {
							if(arr[cy][cx]) continue;
							vir = min(vir, solve());
						}
				}
		}
	cout << n * m - vir - wal - 3;
}