[백준 17142] 연구소 3

문제 링크 :  17142번: 연구소 3 (acmicpc.net)

17142번: 연구소 3

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 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 + 완전 탐색 문제이다.

모든 경우를 다 따져야 하는 문제이다.

모든 경우를 다 따질 수 있는 이유는 입력에서 연구소에 놓일 바이러스의 갯수가 10 이하이기 때문에 충분하다.

 

문제 풀이는 다음과 같다.

1. 바이러스를 담을 벡터 v를 가지고 벡터의 인덱스 0을 시작으로 하여 바이러스를 놓을 것인지, 놓지 않을 것인지 2가지 경우로 재귀적 호출을 한다.

이때 재귀적 호출은 solution(idx, cnt) 으로 idx 는 벡터의 인덱스, cnt 는 연구소에 놓은 바이러스의 갯수를 의미한다.

메인 함수에서 solution(0, 0) 을 호출하여 인덱스 0, 놓은 바이러스 갯수 0으로 시작하게끔 한다.

 

2. 바이러스를 놓을 경우와 놓지 않을 경우 두가지로 나뉜다.

(1) 바이러스를 놓을 경우 : 임시 배열을 선언함으로써 전파되기 전의 상태를 미리 보관한다.

그 후에 바이러스를 전파시키고 재귀 호출이 끝나면 다시 전파되기 전의 상태로 복구한다.

바이러스를 전파하는 방식은 다음과 같이 구현하였다.

void set_virus(int startX, int startY) {
	queue<pair<pair<int, int>, int>> Q;

	init();
	Q.push({ {startX,startY},0 });
	virus[startX][startY] = 0;
	check[startX][startY] = true;
	while (!Q.empty()) {
		int x = Q.front().first.first, y = Q.front().first.second;
		int cnt = Q.front().second;
		Q.pop();

		for (int i = 0; i < 4; i++) {
			int nextX = x + dx[i], nextY = y + dy[i];
			if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
				if (!check[nextX][nextY]) {
					if (Map[nextX][nextY] == 0) {
						check[nextX][nextY] = true;
						if (cnt + 1 < virus[nextX][nextY]) virus[nextX][nextY] = cnt + 1;
						Q.push({ {nextX,nextY}, virus[nextX][nextY] });
					}
					else if (Map[nextX][nextY] == 2) {
						check[nextX][nextY] = true;
						Q.push({ {nextX,nextY}, cnt + 1 });
					}
				}
			}
		}
	}
}

 

이때 재귀 호출은 solution(idx + 1, cnt + 1) 을 호출함으로써 벡터의 인덱스와 바이러스의 갯수를 1 증가시켜서 인자를 넘겨주는 방식이다.

(2) 바이러스를 놓지 않을 경우 : solution(idx + 1, cnt) 을 호출함으로써 벡터의 인덱스만 1 증가시켜서 인자를 넘겨준다.

 

3. solution(idx, cnt) 에서 idx, cnt, 그리고 바이러스 총 갯수를 가지고 케이스를 나눠야 한다.

(1) cnt = M : 바이러스 M개가 연구소에 놓인 상태이다.

바이러스가 연구소에 전부 퍼진 경우 전파된 최대 시간이 결국 전파된 시간이다.

전역변수 result 를 선언함으로써 전파된 시간을 비교하며 작을 경우 해당 값을 할당해주면 된다.

이때 전역변수 result의 초기값을 INF(1,000,000,000) 으로 설정해주자.

(2) 바이러스 총 갯수 - idx + cnt < M : 예를 들어 바이러스 갯수가 10개이며 놓아야 할 바이러스의 갯수는 5개이며 (5, 0), (6, 0) 두 가지 경우를 생각해보자.

(5, 0) 일 경우 아직 바이러스를 놓을 수 있는 기회가 존재한다.

그러나 (6, 0) 일 경우 계속해서 바이러스를 놓을지라도 (10, 4) 으로 놓아야 할 바이러스의 갯수에 미치지 못한다.

따라서 바이러스 총 갯수 - idx + cnt 값이 M 보다 작을 경우 더이상 진행이 불가능하기 때문에 단순히 리턴을 해주면 된다.

 

4. 이렇게 해서 result 값을 구하였다.

result 값이 INF 즉, 연구소에 바이러스가 전부 전파되지 못한 경우 -1을 출력하고 그렇지 않은 경우 result 값을 출력하면 된다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N, M, result;
int Map[51][51], virus[51][51];
bool check[51][51];
vector<pair<int, int>> v;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void input() {
	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) v.push_back({ i,j });
			virus[i][j] = INF;
		}
	}
}

void copy_virus(int src[][51], int dest[][51]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			dest[i][j] = src[i][j];
		}
	}
}

void init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			check[i][j] = false;
		}
	}
}

void set_virus(int startX, int startY) {
	queue<pair<pair<int, int>, int>> Q;

	init();
	Q.push({ {startX,startY},0 });
	virus[startX][startY] = 0;
	check[startX][startY] = true;
	while (!Q.empty()) {
		int x = Q.front().first.first, y = Q.front().first.second;
		int cnt = Q.front().second;
		Q.pop();

		for (int i = 0; i < 4; i++) {
			int nextX = x + dx[i], nextY = y + dy[i];
			if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
				if (!check[nextX][nextY]) {
					if (Map[nextX][nextY] == 0) {
						check[nextX][nextY] = true;
						if (cnt + 1 < virus[nextX][nextY]) virus[nextX][nextY] = cnt + 1;
						Q.push({ {nextX,nextY}, virus[nextX][nextY] });
					}
					else if (Map[nextX][nextY] == 2) {
						check[nextX][nextY] = true;
						Q.push({ {nextX,nextY}, cnt + 1 });
					}
				}
			}
		}
	}
}

void solution(int idx, int cnt) {
	if (cnt == M) {
		int ret = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (Map[i][j] == 0) {
					if (virus[i][j] == INF) return;
					ret = max(ret, virus[i][j]);
				}
			}
		}
		result = min(result, ret);
		return;
	}
	if (v.size() - idx + cnt < M) return;
	int tmp[51][51];


	// 바이러스 세팅
	copy_virus(virus, tmp);
	set_virus(v[idx].first, v[idx].second);
	solution(idx + 1, cnt + 1);
	copy_virus(tmp, virus);

	// 바이러스 노세팅
	solution(idx + 1, cnt);
}

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

	input();
	result = INF;
	solution(0, 0);
	cout << (result == INF ? -1 : result);

	return 0;
}