문제

https://www.acmicpc.net/problem/14502

풀이

벽은 1, 바이러스는 2, 아무것도 없으면 0으로 표시되는 크기가 N X M(3 <= N,M <= 8)인 연구소가 있다.

벽 3개를 무조건 세워 바이러스가 퍼지지 않은 최대 공간을 구하는 문제이다.

벽 3개를 임의로 세워야 하는데 어떤 규칙이 있는지 생각해 보았다. 마땅한 규칙이 떠오르지 않아 완전 탐색으로 0(빈 공간) 3개의 자리를 선택하는 조합밖에 없다고 생각하였다.따라서 dfs 조합을 활용하여 벽을 세워줄 0 공간 3개를 선택하였다.

벽을 3개 세워줬다면 그 다음 할 일은 BFS를 통해 바이러스가 퍼진 공간을 만드는 것이다. 이 때 주어진 배열은 다시 사용해야 하므로 새로운 배열에 복사하여 BFS를 사용해야 한다. (2차원 배열 복사가 익숙치 않아 시간이 좀 걸렸다.)

BFS가 끝났다면 안전한 영역(0)의 개수를 세주고 벽을 3개 세우는 모든 경우의 수 중 가장 많은 안전한 영역을 구하면 됐다.

BFS를 떠올리는 것은 어렵지 않았지만 벽을 3개 세우는 방법에서 완전 탐색을 떠올리고 조합으로 정확한 구현을 하는 것이 핵심이었다.

또한 반복이 필요할 때는 배열을 복사하여 재사용할 수 있게하는 방법이 익숙치 않았는데 이 문제를 경험삼아 거부감이 없도록 연습해야겠다.

코드

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

int N, M;
int board[9][9];
int boardCopy[9][9];
vector<p> v;
int res = 0;
int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };

bool visited[9][9];

void BFS(int y, int x) {

	visited[y][x] = true;
	queue<p> q;
	q.push({ y,x });

	while (!q.empty()) {
		y = q.front().first;
		x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int curY = y + dy[i];
			int curX = x + dx[i];
			if (curY <= 0 || curY > N || curX <= 0 || curX > M)
				continue;
			if (boardCopy[curY][curX] == 0 && !visited[curY][curX]) {
				visited[curY][curX] = true;
				boardCopy[curY][curX] = 2;
				q.push({ curY,curX });
			}
		}
	}

}

void BFSInit() {
	
	memcpy(boardCopy, board, sizeof(board));
	for (int i = 0; i < 9; i++)
		memset(visited[i], 0, sizeof(visited[i]));

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (boardCopy[i][j] == 2 && !visited[i][j]) {
				BFS(i, j);
			}
		}
	}

	int cnt = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (boardCopy[i][j] == 0)
				cnt++;
		}
	}
	res = max(res, cnt);
}

void DFS(int idx, int level) {
	if (level == 3) {
		BFSInit();
		return;
	}

	for (int i = idx; i < v.size(); i++) {
		if (board[v[i].first][v[i].second] == 0) {
			board[v[i].first][v[i].second] = 1;
			DFS(i + 1, level + 1);
			board[v[i].first][v[i].second] = 0;
		}
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> board[i][j];
			if (board[i][j] == 0)
				v.push_back({ i,j });
		}
	}

	DFS(0, 0);

	cout << res;

	return 0;
}