연구소 (feat. 백준, 14502번)

연구소
https://www.acmicpc.net/problem/14502

14502번: 연구소

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, ans, dx[4], dy[4], arr[9][9];
bool check[9][9], visit[9][9];
vector<pair<int, int>> virus;
int bfs(int(*maps)[9]) {
	memset(visit, false, sizeof(visit));
	queue<pair<int, int>> q;
	for (auto& p : virus) {
		q.push(p);
		visit[p.first][p.second] = true;
	}
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		register int x = p.first, y = p.second;
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = x + dx[d], ny = y + dy[d];
			if (1 <= nx && nx <= N && 1 <= ny && ny <= M && !visit[nx][ny] && maps[nx][ny] == 0)
				visit[nx][ny] = true, maps[nx][ny] = 2, q.push(make_pair(nx, ny));
		}
	}
	register int answer = 0;
	for (register int i = 1, j; i <= N; ++i)
		for (j = 1; j <= M; ++j)
			if (maps[i][j] == 0)
				++answer;
	return answer;
}
void built_walls(register int x, register int y, register int count) {
	if (count == 3) {
		int tmp[9][9];
		memcpy(tmp, arr, sizeof(tmp));
		ans = max(ans, bfs(tmp));
		return;
	}
	for (register int i = x, j; i <= N; ++i) {
		for (j = y; j <= M; ++j)
			if (!check[i][j] && arr[i][j] == 0) {
				check[i][j] = true;
				arr[i][j] = 1;
				built_walls(i, j + 1, count + 1);
				check[i][j] = false;
				arr[i][j] = 0;
			}
		y = 1;
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> N >> M;
	for (register int n = 1, m; n <= N; ++n)
		for (m = 1; m <= M; ++m) {
			cin >> arr[n][m], check[n][m] = false;
			if (arr[n][m] == 2)
				virus.push_back(make_pair(n, m));
		}
	built_walls(1, 1, 0);
	cout << ans;
	return 0;
}
// *&)*@*

 

1. dfs와 bfs를 모두 사용하여 풀이하였습니다.
2. 벽을 3개 세워야하며 이 벽은 조합으로 구성되어야 합니다. 따라서 이는 dfs를 통해 구할 수 있습니다. (built_walls)
3. 2번에서 벽을 세운 후 문제에서 주어진 바이러스 위치를 기준으로 상,하,좌,우 로 퍼트리고 전체에 0이 몇개가 있는지를 확인합니다.
4. 2번과 3번을 반복하며 이중 가장 큰 값을 구하여 출력합니다.