[C++]백준 14502 - 연구소

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX 8
using namespace std;

int n, m;
int virus[MAX][MAX];
int temp[MAX][MAX];

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

	
int bfs() {
	queue<pair<int, int>> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			temp[i][j] = virus[i][j];
			if (temp[i][j] == 2)
				q.push(make_pair(i, j));
		}
	}

	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 + dx[i];
			int ny = y + dy[i];

			if (0 <= nx && nx < n && 0 <= ny && ny < m) {
				if (temp[nx][ny] == 0) {
					temp[nx][ny] = 2;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}
	int safe_zone = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (temp[i][j] == 0)
				safe_zone++;
		}
	}

	return safe_zone;
}


int main() {

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> virus[i][j];
		}
	}

	int max_safe = 0;

	//여기 벽 세우는 부분은 외부 코드 참조함......

	for (int w1 = 0; w1 < n; w1++) {
		for (int w2 = 0; w2 < m; w2++) {
			if (virus[w1][w2] != 0) {
				continue;
			}
			for (int q1 = 0; q1 < n; q1++) {
				for (int q2 = 0; q2 < m; q2++) {
					if (virus[q1][q2] != 0)
						continue;
					for (int e1 = 0; e1 < n; e1++) {
						for (int e2 = 0; e2 < m; e2++) {
							if (virus[e1][e2] != 0)
								continue;

							if (w1 == q1 && w2 == q2)
								continue;
							if (w1 == e1 && w2 == e2)
								continue;
							if (q1 == e1 && q2 == e2)
								continue;

							virus[w1][w2] = 1;
							virus[q1][q2] = 1;
							virus[e1][e2] = 1;

							int safe = bfs();
							if (safe > max_safe)
								max_safe = safe;

							virus[w1][w2] = 0;
							virus[q1][q2] = 0;
							virus[e1][e2] = 0;
						}
					}
				}
			}
		}
	}
	cout << max_safe << '\n';

	return 0;
}