개발 블로그

문제 링크 : www.acmicpc.net/problem/17142

문제

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

접근 방법

전체 바이러스 중에 DFS를 활용한 중복조합을 이용해서 M개를 픽해준다. (활성 상태로 만들 바이러스 선택)

활성상태로 만들 바이러스를 queue에 넣고 BFS를 돌면서 fromStart배열 요소를 하나씩 증가해 나간다.

여기서 주의해야할 경우는 다음에 방문할 칸인 fromStart[nr][nc]가 빈칸이 아닌 비활성 상태의 바이러스인 경우이다. 

* 비활성 바이러스를 활성 바이러스 상태로 바꾸는데에는 1초가 소요되지 않는다. (문제 조건에는 빈칸->바이러스 상태가 되는 경우에 1초가 소요된다고만 나와있기 때문)

그리고 fromStart[nr][nc]들의 값을 비교해서 가장 큰 값을 ansVec에 push 해야하는데 (넣어놓고 마지막에 모든 빈칸에 바이러스가 퍼지기까지 걸리는 최소시간 구하기 위함) 그 fomStart[nr][nc]의 값을 최대인지 비교하는 조건문은 다음에 방문할 칸이 빈 칸인 경우에만 실행되도록 한다. (

이러한 로직으로 풀면 답이 통과된다. 

#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;

int map[50][50];
vector<pair<int, int>> initVirus;	//처음 2(바이러스) 위치
int visited[10] = { 0 };			//처음 2(바이스) 활성 선택 여부
vector<int> virusIdx;				//전체 바이러스 중 M개를 담는 벡터
//위 오 아 왼
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
int N, M;
int space = 0;	//빈칸
vector<int> ansVec;
void spreadBFS() {

	int maxSecond = 0;
	int fromStart[50][50];
	int initLoc[50][50];
	memset(fromStart, 0, sizeof(fromStart));
	memset(initLoc, 0, sizeof(initLoc));
	queue<pair<int, int>> que;
	int cnt = 0;

	for (int i = 0; i < virusIdx.size(); i++) {	//M개
		que.push(initVirus[virusIdx[i]]);
		initLoc[initVirus[virusIdx[i]].first][initVirus[virusIdx[i]].second] = 1;		//처음 바이러스가 있던 시작점
	}
	while (!que.empty()) {
		int r = que.front().first;
		int c = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (nr < 0 || nr >= N || nc < 0 || nc >= N ||		//범위 벗어나거나
				map[nr][nc] == 1 || fromStart[nr][nc] != 0 || initLoc[nr][nc] == 1) continue;	//벽이거나, 이미 바이러스 퍼졌거나, 처음 활성바이러스 위치면 스킵

			//빈칸이던 비활성바이러스이던 둘 다
			fromStart[nr][nc] = fromStart[r][c] + 1;
			que.push(make_pair(nr, nc));

			//비활성 바이러스 아니고 빈칸인 경우에
			if (map[nr][nc] == 0) {
				cnt++;		//빈칸에서 바이러스 상태 된 칸의 수 카운트
				if (maxSecond < fromStart[nr][nc]) maxSecond = fromStart[nr][nc];	//이 경우에만 최대로 걸린 초 고려하기
			}

		}

	}

	if (cnt == space) {			//모든 빈칸에 다 퍼졌으면 
		ansVec.push_back(maxSecond);
	}
}


void pickDFS(int toPick, int start) {			//전체 바이러스 중 M개 픽

	if (toPick == 0) {
		spreadBFS();
	}

	for (int i = start; i < initVirus.size(); i++) {
		if (visited[i] == 0) {
			visited[i] = 1;
			virusIdx.push_back(i);
			pickDFS(toPick - 1, i);
			virusIdx.pop_back();
			visited[i] = 0;
		}
	}
}


int main() {

	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) {
				initVirus.push_back(make_pair(i, j));
			}
			else if (map[i][j] == 0) space++;
		}
	}


	//initVec에서 활성상태로 만들 바이러스 M개 고르기
	pickDFS(M, 0);

	if (ansVec.size() == 0) cout << -1;
	else {
		sort(ansVec.begin(), ansVec.end());
		cout << ansVec[0];
	}
	return 0;
}