백준 - 연구소 3 (17142번)

백준 - 연구소 3 (17142번)

dfs + bfs로 풀 수 있는 문제다.
인풋 맵으로 받을 때, 모든 바이러스에 대해서 M개만큼 조합을 구하기 위해 DFS를 돌리면서 조합을 구한다.
구해진 조합은 "활성 바이러스"가 되는 것이다. 이를 기준으로 BFS를 수행하면서 맵에 바이러스를 퍼뜨려주면 된다.
또한 바이러스가 퍼질 수 있는 경우를 상하좌우로 체크하면서 BFS를 수행해주면서 Time을 업데이트해주고, 만약 바이러스가 온 맵에 퍼질 수 있다면 정답을 조건에 맞도록 업데이트해주면 된다.

내 구현에서 하나 까다로웠던 점은 "활성 바이러스가 비활성 바이러스가 잇는 칸으로 가면 비활성 바이러스가 활성으로 변한다." 조건이었는데, 이 때문에 만약 바이러스가 퍼지는 지점이 비활성화 바이러스가 있는 곳이었다면 Time을 업데이트해주지 않았다.
다행히 테스트케이스 1번에서 예외를 만날 수 있어서 금방 해결했다.

코드는 아래와 같다.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef struct __pos {
	int row;
	int col;
	int time;
}pos;
int n, m, nn;
int map[64][64];
int copy_map[64][64];
int visitMap[64][64];
pos virus[16];

int candidate[16];
int visit[16];
int answer;
int rowDir[4] = { -1, 0, 1, 0 };
int colDir[4] = { 0, 1, 0, -1 };
bool can_solve;
void solve()
{
	queue<pos> q;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) {
			visitMap[i][j] = 0;
			copy_map[i][j] = map[i][j];
		}
	

	for (int i = 0; i < m; i++) 
		q.push({ virus[candidate[i]].row, virus[candidate[i]].col, 0 });
	
	int time = 0;
	while (1) {
		if (q.empty())
			break;

		pos cur = q.front(); q.pop();
		if (visitMap[cur.row][cur.col])
			continue;
		visitMap[cur.row][cur.col] = 1;
		if(copy_map[cur.row][cur.col] != 2)
			time = max(time, cur.time);
		copy_map[cur.row][cur.col] = -1;
		for (int i = 0; i < 4; i++) {
			int nrow = cur.row + rowDir[i];
			int ncol = cur.col + colDir[i];

			if (nrow < 0 || ncol < 0 || nrow > n - 1 || ncol > n - 1)
				continue;
			if (visitMap[nrow][ncol])
				continue;
			if (copy_map[nrow][ncol] == 1) 
				continue;
			
			q.push({ nrow, ncol, cur.time + 1 });
		}
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (copy_map[i][j] == 1 || copy_map[i][j] == -1 || copy_map[i][j] == 2)
				cnt++;

	if (cnt == nn) {
		answer = min(answer, time);
		can_solve = true;
	}
}
void dfs(int m, int depth, int s)
{
	if (depth == m) {
		solve();
		return;
	}
	
	for (int i = 0; i < s; i++) {
		if (visit[i])
			continue;
		if (depth > 0 && i <= candidate[depth - 1])
			continue;
		visit[i] = 1;
		candidate[depth] = i;
		dfs(m, depth + 1, s);
		visit[i] = 0;
	}
}

int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	answer = 1 << 20;
	can_solve = false;
	int total_virus_num = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) 
				virus[total_virus_num++] = { i, j };
		}
	nn = n * n;
	dfs(m, 0, total_virus_num);
	if (!can_solve)
		answer = -1;

	cout << answer << "\n";

	return 0;
}