[14502] 연구소

풀이

1. 0의 위치를 모두 벡터 v에 넣는다.
2. v 길이와 같은 1,1,1,0,0,…,0으로 채워진 vector v2를 만든다.
3. v2를 prev_permutation하면서 v2가 1인 idx의 v의 값이 나타내는 위치에 벽을 세운다.
4. bfs를 통해서 바이러스를 전파시킨다.
5. 남은 0의 갯수를 세서 갱신한다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
bool check[8][8];
int map2[8][8];
vector<pair<int, int> >v;
void bfs(int i, int j, int n, int m) {
	
	queue<pair<int, int> > q;
	q.push(make_pair(i, j));
	check[i][j] = true;
	while (!q.empty()) {
		pair<int, int> curr = q.front(); q.pop();
		int nx = 0, ny = 0;
		for (int k = 0; k < 4; k++) {
			nx = curr.first + dx[k];
			ny = curr.second + dy[k];
			if (nx < 0 || nx >= n) continue;
			if (ny < 0 || ny >= m) continue;
			if (map2[nx][ny] == 0){
				if (check[nx][ny] == false) {
					map2[nx][ny] = 2;
					check[nx][ny] = true;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}
}
int main(void) {
	//맵 입력받기
	int map[8][8];
	int n = 0, m = 0;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 0) {
				v.push_back(make_pair(i, j));
			}
		}
	}
	//prev_permutation에 쓰이는 vector
	vector<int> arr(v.size(), 0);  arr[0] = 1; arr[1] = 1; arr[2] = 1;
	//정답이 저장될 변수
	int ans = 0; 
	do {
		for (int a = 0; a < n; a++) {
			memset(check[a], false, sizeof(check[a]));
		}
		//복사
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map2[i][j] = map[i][j];
			}
		}
		//3개를 벽으로 만들기
		for (int k = 0; k < v.size(); k++) {
			if (arr[k] == 1) {
				map2[v[k].first][v[k].second] = 1;
			}
		}
		//2를 확산
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map2[i][j] == 2 && check[i][j] == false) {
					bfs(i, j,n,m);
				}
			}
		}
		//0 벽의 갯수를 세기
		int white = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map2[i][j] == 0) white += 1;
			}
		}
		//printf("white is %d개\n", white);
		ans = max(ans, white);
	} while (prev_permutation(arr.begin(), arr.end()));
	//빈칸인 모든 좌표 중 3개를 선택해서 1로 만드는 next_permutation
	printf("%d\n", ans);
	return 0;
}