백준 17142 연구소 3 C++

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

* 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 *

시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
* - 3 2 3 4 *

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

입력

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

 

풀이

이 문제는 주어진 연구소에서 바이러스를 퍼뜨려 모든 빈 칸을 바이러스로 채우는 최소 시간을 구하는 문제이다.

BFS(너비 우선 탐색)와 조합으로 해결한다.

 

문제 설명:

연구소는 N x N 격자 형태이다. 격자 셀은 빈칸, 벽, 또는 바이러스 중 하나가 될 수 있다.

목표는 모든 빈 칸을 바이러스로 채우는데 걸리는 최소 시간을 구한다.

바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며 벽은 통과할 수 없다.

초기에 바이러스가 이미 퍼져 있는 몇몇 위치가 주이진다. 초기 모든 바이러스는 비활성상태이다.

특정 바이러스를 활성화시킬 수 있는데, 활성화된 바이러스는 퍼질 수 있으며, 비활성화된 바이러스는 퍼지지 않는다.

활성화된 바이러스를 M개를 선택하여 활성화시키고, 최소시간을 구해야 한다.

 

해결방법:

1. 먼저, 주어진 연구소의 상태를 입력받는다. 빈 칸(0), 벽(1), 바이러스(2)를 구분하여 저장한다.

2. 활성화된 바이러스 중 M개를 선택하는 모든 조합을 생성한다. 이는 재귀 함수를 사용하거나 비트마스크를 활용할 수 있다.

3. 각 조합별로 BFS를 사용하여 바이러스를 퍼뜨린다. 즉, 선택한 활성화된 바이러스로부터 시작하여 BFS를 수행하면서 바이러스를 퍼뜨리는 과정을 시뮬레이션한다.

4. BFS를 수행하면서 모든 빈 칸을 바이러스로 채울 때까지의 시간을 측정한다.

5. 위의 과정을 모든 과정에 대해 반복하고, 그 중에서 최소 시간을 찾아 출력한다.

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#define MAX 50
#define INF 987654321
using namespace std;

int n, m, emptyPlace, answer = INF;
int map[MAX][MAX];
int time[MAX][MAX];
bool select[10];

vector<pair<int, int>> virus;

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };


void spreadVirus(queue<pair<int, int>> q){
	int infectPlace = 0;
	int totalTime = 0;
	while (q.empty() == 0){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx >= 0 && ny >= 0 && nx < n && ny < n){
				if (map[nx][ny] != 1 && time[nx][ny] == -1){
					time[nx][ny] = time[x][y] + 1;
					if (map[nx][ny] == 0){
						infectPlace++;
						totalTime = time[nx][ny];
					}
					q.push(make_pair(nx, ny));
				}
			}
		}
	}
	if (infectPlace == emptyPlace){
		answer = min(answer, totalTime);
	}
}

void selectVirus(int idx, int cnt){
	if (cnt == m){
		queue<pair<int, int>> q;
		memset(time, -1, sizeof(time));
		for (int i = 0; i < virus.size(); i++){
			if (select[i] == true){
				q.push(make_pair(virus[i].first, virus[i].second));
				time[virus[i].first][virus[i].second] = 0;
			}
		}

		spreadVirus(q);
		return;
	}

	for (int i = idx; i < virus.size(); i++){
		if (select[i] == true) {
			continue;
		}
		select[i] = true;
		selectVirus(i + 1, cnt + 1);
		select[i] = false;
	}
}


int main(void){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	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] == 0) {
				emptyPlace++;
			}
			else if (map[i][j] == 2) {
				virus.push_back(make_pair(i, j));
			}
		}
	}
	
	selectVirus(0, 0);
	if (answer == INF) {
		cout << -1 << '\n';
	}
	else {
		cout << answer << '\n';
	}

	return 0;
}