[백준] 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을 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>

using namespace std;

struct pos
{
	int r;
	int c;

	void init(int r, int c)
	{
		this->r = r;
		this->c = c;
	}
};

int N;
int M;
int lab[51][51];		// 연구소의 상태
int inactive;			// 빈칸의 개수
vector<pos> birus;		// 비활성 바이러스가 있는 칸

// 배치된 비활성 바이러스 중에서 어떤 바이러스를 활성 상태로 바꿀 것인지 선택하는 순열
// 오름차순으로 초기화하여 모든 경우를 확인하는데 사용
string make_permutation()
{
	string res = "";
	int i;

	for (i = 0; i < M; i++)
		res += '1';
	for (i = M; i < birus.size(); i++)
		res += '0';
	sort(res.begin(), res.end());
	return res;
}

// 주어진 좌표가 범위 내인지 확인
bool in_range(pos p)
{
	if (p.r < 0 || p.r >= N || p.c < 0 || p.c >= N)
		return false;
	return true;
}

// 모든 빈칸에 바이러스를 퍼뜨리기 위한 시간을 구함
int spreed_birus(string per)
{
	queue<pos> q;
	pos curr, next;
	int visit[51][51];			// 해당 칸에 바이러스를 퍼뜨리기 위한 시간
	int d[] = {-1, 1, 0, 0};		// 상하좌우로 퍼뜨림
	int cnt = 0;				// 바이러스가 퍼진 칸의 수
	int i, time = 0;			// 현재까지 걸린 시간

	// 초기화
	memset(visit, -1, sizeof(visit));

	// 활성 상태로 바꾼 바이러스의 좌표를 큐에 삽입
	// 활성 상태로 바꿀 때의 시간은 0임
	for (i = 0; i < per.size(); i++)
	{
		if (per[i] == '1')
		{
			next = birus[i];
			visit[next.r][next.c] = 0;
			q.push(next);
		}
	}
	while (!q.empty())
	{
		curr = q.front();
		q.pop();
		// 상하좌우로 바이러스를 퍼뜨림
		for (i = 0; i < 4; i++)
		{
			next.init(curr.r + d[i], curr.c + d[3 - i]);
			// 범위 밖이면 패스
			if (!in_range(next))
				continue;
			// 벽이면 패스
			if (lab[next.r][next.c] == 1)
				continue;
			// 이미 바이러스가 있으면 패스
			if (visit[next.r][next.c] != -1)
				continue;
			// 걸린 시간을 저장하고 큐에 삽입
			visit[next.r][next.c] = visit[curr.r][curr.c] + 1;
			q.push(next);
			// 원래 바이러스가 없던 칸인 경우
			// 개수를 세고 현재까지 걸린 시간을 갱신
			if (lab[next.r][next.c] == 0)
			{
				cnt++;
				time = visit[next.r][next.c];
			}
		}
	}
	// 모든 빈칸에 바이러스가 퍼진 경우
	if (cnt == inactive)
		return time;
	// 모든 빈칸에 바이러스가 퍼지지 않은 경우
	return -1;
}

int main()
{
	int i, j;
	int res, answer = INT_MAX;
	string per = "";
	pos p;

	cin >> N >> M;
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			cin >> lab[i][j];
			if (lab[i][j] == 0)
			{
				inactive++;
			}
			if (lab[i][j] == 2)
			{
				p.init(i, j);
				birus.push_back(p);
			}
		}
	}
	// 모든 경우를 확인하여 최소 시간을 구함
	per = make_permutation();
	do
	{
		res = spreed_birus(per);
		if (res != -1)
			answer = min(answer, res);
	} while (next_permutation(per.begin(), per.end()));
	if (answer == INT_MAX)
		cout << -1 << endl;
	else
		cout << answer << endl;
	return 0;
}

 

연구소 2에서는 입력값을 처리한 후 연구소의 상태가 빈칸(0)과 벽(1)으로 표현되었다. 연구소 3에서는 빈칸(0)과 벽(1), 비활성 바이러스가 있는 칸(2)으로 표현된다. 새롭게 바이러스를 추가하는 것이 아니라 이미 존재하는 바이러스의 상태만 바꾸는 것이기 때문에 연구소 2와 다르게 값이 2인 칸을 0으로 바꿔주지 않는다. 또한 모든 빈칸으로 바이러스를 퍼트리는데 걸리는 시간을 측정하기 때문에 비활성 바이러스가 활성 바이러스로 바뀌는 경우에는 개수를 세거나 걸린 시간(time)을 갱신하지 않는다.

[백준] 17141번 - 연구소 2 / C++

 

링크

17142번: 연구소 3

inbdni/Baekjoon