[백준 14502번 - 연구소] C++ 풀이

백준 14502번.

벽 3개를 추가로 세워서 바이러스가 퍼지지 않는 안전영역의 최대값을 구하는 문제이다.

 

사용한 알고리즘

- 브루트포스

- bfs

 

처음에는 벽 3개를 치는 경우의 수중 쳐낼 수 있는 가지수가 없나 생각을 해봤는데, 내 머리로는 도저히 떠오르지 않아서 그냥 다 구해보기로 했다. 3 <= N, M <= 8 이므로, map 최대 크기는 2의 6승. 그리고 벽 3개를 칠 가지수는 약 2의 18승 = 약 262,144개 이고, 각 경우의 수에 bfs 를 돌릴 경우 약 2의 12승, 더하면 약 2의 30승...... 대략 10억... 안되겠는데? 싶었지만 일단 코드를 짜서 제출했는데 맞았다... 뭐지..? 1과, 2가 이렇게 극한의 최대치로 주어진 테스트케이스가 없나? 1, 2가 있는 곳 때문에 실제 벽을 치는 가지수가 훨씬 적나.?.

 

우선 벽을 칠 수 있는 경우의 수를 모두 구한다. (난 재귀로 했다.)

각 경우에 대해 bfs 를 돌려서 바이러스가 다 퍼져나간 상태의 map 을 구한다. 해당 map 의 안전영역 크기(= 0인 곳의 갯수) 를 구한다.

완성된 코드

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> map;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
vector<pair<int, int>> two_loc;
int n, m;
int ans = 0;

int bfs(vector<vector<int>> map) {
	queue<pair<int, int>> q;
	int result = 0;
	for(int i = 0; i < two_loc.size(); ++i) {
		q.push(make_pair(two_loc[i].first, two_loc[i].second));
		while(!q.empty()) {
			int cur_x = q.front().first;
			int cur_y = q.front().second;
			q.pop();
			for(int i = 0; i < 4; ++i) {
				int nx = cur_x + dx[i];
				int ny = cur_y + dy[i];
				if (nx < 0 || ny < 0 || nx >= n || ny >= m || map[nx][ny] == 1 || map[nx][ny] == 2) {
					continue;
				} else {
					q.push(make_pair(nx, ny));
					map[nx][ny] = 2;
				}
			}
		}
	}
	// 안전 영역 크기 구하기.
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			if (map[i][j] == 0)
				result++;
		}
	}
	return ans < result ? result : ans;
}

//벽세우기
void partition(int l, vector<vector<int>> map) {
	if (l == 4) {
		// 해당 맵의 안전 영역 크기 구한다.
		ans = bfs(map);
		//printf("maximum = %d\n", ans);
	} else {
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < m; ++j) {
				if (map[i][j] == 0) {
					map[i][j] = 1;
					partition(l + 1, map);
					map[i][j] = 0;
				}
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);

	map.assign(n + 1, vector<int>(m + 1, 0));
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2) {
				two_loc.push_back(make_pair(i, j));
			}
		}
	}

	partition(1, map);
	printf("%d\n", ans);
}