14502번 연구소

음.. 처음 생각에는 일일이 3개의 벽을 세워두고 BFS를 쓰면 되지 않을까 생각했었다. 그런데 너무 비효율적이진 않을까? 라는 생각에 계속해서 고민해보았다. 그런데 그게 맞았다. 시간복잡도와 브루트포스에 대한 자신감을 가지고 해야겠다.

#include <iostream>
#include <algorithm>
#include <queue>
int map[9][9];
int ch[9][9];
int cnt = 0, res = -2147000000;
int n, m;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
using namespace std;
void BFS() {
	queue<pair<int, int>> Q;
	cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ch[i][j] = map[i][j];
			if (ch[i][j] == 2) Q.push(make_pair(i, j));
		}
	}
	while (!Q.empty()) {
		//cout << "error";
		int x = Q.front().first;
		int y = Q.front().second;
		Q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx > n || xx<1 || yy>m || yy < 1) continue;
			if (ch[xx][yy] == 1 || ch[xx][yy] == 2) continue;
			if (ch[xx][yy] == 0) {
				ch[xx][yy] = 2;
				Q.push(make_pair(xx, yy));
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (ch[i][j] == 0) cnt++;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	//freopen("in1.txt", "rt", stdin);
	int i, j, k, x1, x2, x3, y1, y2, y3;
	cin >> n >> m;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			cin >> map[i][j];
		}
	}
	for (x1 = 1; x1 <= n; x1++) {
		for (y1 = 1; y1 <= m; y1++) {
			if (map[x1][y1] != 0) continue;
			for (x2 = 1; x2 <= n; x2++) {
				for (y2 = 1; y2 <= m; y2++) {
					if (map[x2][y2] != 0) continue;
					for (x3 = 1; x3 <= n; x3++) {
						for (y3 = 1; y3 <= m; y3++) {
							if (map[x3][y3] != 0) continue;
							if (x1 == x2 && y1 == y2) continue;
							if (x1 == x3 && y1 == y3) continue;
							if (x2 == x3 && y2 == y3) continue;
							map[x1][y1] = 1;
							map[x2][y2] = 1;
							map[x3][y3] = 1;
							//cout << "map ";
							BFS();
							if (res < cnt) res = cnt;
							map[x1][y1] = 0;
							map[x2][y2] = 0;
							map[x3][y3] = 0;
						}
					}
				}
			}
		}
	}
	cout << res << '\n';
	return 0;
}