문제

문제 링크

해설

• 연구실의 크기는 최대 8×8이고, 놓을 수 있는 벽의 개수가 3개이므로
  • 최악의 경우, 바이러스가 연구실에 벽이 하나도 없고, 바이러스가 딱 2곳 있다면
  • 3개의 벽을 세울 수 있는 경우는 62 x 61 x 60이고
  • 각 경우의 수마다 DFS로 바이러스를 전파하고, 안전영역의 넓이를 카운팅하는 것까지 계산하면
  • 1초안에 풀 수 있음을 알 수 있습니다.
• 그러므로 벽을 놓을 수 있는 모든 경우에 대해 DFS 또는 BFS를 수행해서 바이러스가 퍼지는 시뮬레이션을 한 뒤 빈 공간의 개수가 가장 많은 경우를 뽑아내면 문제를 풀 수 있습니다.
• 이때, 벽을 두는 행위, 바이러스가 퍼지는 행위 모두 입력받은 연구실 정보에 영향을 주기 때문에 매 경우마다 연구실을 복사한 뒤 복사본에 대해 계산해야 합니다.

코드

#include <iostream>
#include <cstring>
using namespace std;

constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int N, M, virus_cnt;
int lab[8][8], lab_copy[8][8];
pair<int, int> virus[10];

int count_safearea() {
	int ret = 0;
	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++)
			if (lab_copy[y][x] == 0) ret++;
	return ret;
}

void DFS(int y, int x) {
	lab_copy[y][x] = 2;
	for (auto i : d) {
		int ny = y + i[0], nx = x + i[1];
		if (0 <= ny && ny < N && 0 <= nx && nx < M && !lab_copy[ny][nx]) DFS(ny, nx);
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	cin >> N >> M;
	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++) {
			cin >> lab[y][x];
			if (lab[y][x] == 2) virus[virus_cnt++] = {y, x};
		}

	int answer = 0;
	for (int i = 0, size = N * M; i < size; i++)
		for (int j = i + 1; j < size; j++)
			for (int k = j + 1; k < size; k++)
				if (!lab[i / M][i % M] && !lab[j / M][j % M] && !lab[k / M][k % M]) {
                    /* copy lab ▶ make 3 walls ▶ DFS ▶ count */
                    memcpy(lab_copy, lab, sizeof(lab));
					lab_copy[i / M][i % M] = lab_copy[j / M][j % M] = lab_copy[k / M][k % M] = 1;
					for (int l = 0; l < virus_cnt; l++) DFS(virus[l].first, virus[l].second);
					answer = max(answer, count_safearea());
				}
	cout << answer << '\n';
	return 0;
}

소스코드 링크

결과