[BOJ/C++] 14502(연구소)

1. Link

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

2. 풀이 과정

1. 2차원 배열에서 어떠한 최대 값 구하기 -> BFS
2. 벽 3개를 설치하는 모든 경우를 탐색 -> Brute Force

• 배열의 크기가 8*8이므로 상당히 넉넉하다는 것을 직관적으로 파악하고, 브루트포스 알고리즘과 bfs를 고민없이 사용하였습니다.

• 우선 3중 for문을 사용하여 2차원 배열에 3개의 벽을 설치합니다.
  추가 벽 설치를 위한 i, j, k for문에서 가장 내부에 있는 k for문 내에 구성된 지도에서의 바이러스 bfs 탐색을 시도하도록 합니다.
  각 bfs에서 바이러스가 퍼지는 정도를 확인 후 가장 적게 퍼진 경우의 수를 정답으로 가져옵니다.

• 약간 재귀 스타일의 코드로 풀어서 살짝 코드가 더럽긴 합니다. 다만 코드 변수를 조금 다듬기만 하면 아마 이해하기 쉬울 코드로 생각하니 코드를 붙여넣어 Ctrl+R+R로 변수명을 변경하여 보시면 금방 이해가 될 것입니다.

3. 정답 코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define p pair<int, int>

int n, m, answer = 64, add = 3;
int area[8][8]{ 0 };
int dx[]{ 0,1,0,-1 };
int dy[]{ 1,0,-1,0 };
queue<p> virus;

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> area[i][j];
			if (area[i][j] == 1) ++add;
			else if (area[i][j] == 2) virus.push({ i,j });
		}
	}
}

void bfs() {
	queue<p> q;
	q = virus;
	bool vis[8][8]{ 0 };
	int ans = 0;
	while (!q.empty()) {
		p cur = q.front(); q.pop();
		++ans;
		for (int dir = 0; dir < 4; ++dir) {
			int x = cur.first + dx[dir];
			int y = cur.second + dy[dir];
			if (x < 0 || y < 0 || x >= n || y >= m) continue;
			if (vis[x][y] || area[x][y] > 0) continue;
			vis[x][y] = 1;
			q.push({ x,y });
		}
	}
	if (answer > ans) answer = ans;
}

void solution() {
	input();
	int sq = n * m;
	for (int i = 0; i < sq - 2; ++i) {
        int xI = i / m, yI = i % m;
		if (area[xI][yI] > 0) continue;
		area[xI][yI] = 1;
		for (int j = i + 1; j < sq - 1; ++j) {
			int xJ = j / m, yJ = j % m;
            if (area[xJ][yJ] > 0) continue;
			area[xJ][yJ] = 1;
			for (int k = j + 1; k < sq; ++k) {
				int xK = k / m, yK = k % m;
                if (area[xK][yK] > 0) continue;
				area[xK][yK] = 1;
				bfs();
				area[xK][yK] = 0;
			}
			area[xJ][yJ] = 0;
		}
		area[xI][yI] = 0;
	}
	cout << n * m - answer - add;
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}