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

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×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 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 5

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

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
5 - 3 2 3 4 5

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

 

입력

첫째 줄에 연구소의 크기 N(5 ≤ 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();
		cnt++;
		// 상하좌우로 바이러스를 퍼뜨림
		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);
			// 현재까지 걸린 시간을 갱신
			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);
				lab[i][j] = 0;
				inactive++;
			}
		}
	}
	// 모든 경우를 확인하여 최소 시간을 구함
	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을 저장한다. 주어진 입력을 모두 저장한 후 lab 배열에는 0과 1만 저장되어 있다. 이제 어떤 좌표에 바이러스를 놓아 퍼뜨릴 것인지 정해 모든 칸에 바이러스를 퍼뜨리는데 걸리는 시간을 측정한다. 이때, 순열을 사용해 모든 경우의 수를 확인할 수 있으며, BFS 알고리즘을 사용해 시간을 구할 수 있다. 모든 칸에 바이러스를 퍼뜨리지 못해 -1이 리턴된 경우에는 최솟값을 갱신하지 않는다. 모든 경우를 확인한 후에도 answer가 INT_MAX이면 어떠한 경우에도 모든 칸에 바이러스를 퍼뜨릴 수 없다는 뜻이므로 -1을 출력한다.

 

링크

17141번: 연구소 2

inbdni/Baekjoon