[ 백준-17142번 / BFS ] 연구소 3 (삼성SW)

1. 문제

---

 

17142번: 연구소 3

연구소 3 성공

 

시간 제한메모리 제한제출정답맞은 사람정답 비율

0.25 초 (하단 참고)

512 MB

12723

3439

2016

25.429%

문제

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

예제 입력 1 복사

7 3 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

예제 출력 1 복사

4

 

 

2. 소스코드

---

1회차

 

- 바이러스가 이미 있는 칸을 어떻게 BFS할지 생각해야 했던 문제.

마지막 칸이 바이러스인 경우, 바이러스 칸을 지나가야 하는 경우, 바이러스 칸이 연속인 경우 등등....

 

- 예상 시간 복잡도

1) 입력 : O(N^2)

2-1) Simulation-순열 : O(10! / m!(10-m)!)

2-2) Simulation-BFS : O(N^2)

예상 시간 복잡도 : 1 + (2-1) x (2-2) = O({10!/m!(10-m)!} x N^2)

 

실제 실행 시간 : 12ms

#pragma warning (disable : 4996)
#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
#include <cstring>

using namespace std;

const int pSize = 50;
int map[pSize][pSize], visited[pSize][pSize];
int n, m, time = 2500, emptyPlace;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

queue<tuple<int, int, int>> que;
vector<pair<int, int>> virusPos;
vector<int> idx;

void Spread() {

	int maxDepth = 0;
	int emp = emptyPlace;
	while (!que.empty())
	{
		auto h = que.front();
		int x = get<0>(h);
		int y = get<1>(h);
		int depth = get<2>(h);
		maxDepth = depth;
		que.pop();

		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx < 0 or ny < 0 or nx >= n or ny >= n) continue;
			if (map[nx][ny] == 1 or visited[nx][ny] != -1) continue;
			if (emp == 0) continue;
			if (map[nx][ny] != 2) emp--;
			visited[nx][ny] = depth + 1;
			que.push(make_tuple(nx, ny, depth + 1));
		}
	}
	if (emp != 0) return;
	else if (time > maxDepth) time = maxDepth;
}

void Simulation() {
	do {
		memset(visited, -1, sizeof(visited));
		for (int i = 0; i < idx.size(); i++) {
			if (idx[i]) {
				int x = virusPos[i].first;
				int y = virusPos[i].second;
				que.push(make_tuple(x, y, 0));
				visited[x][y] = 0;
			}
		}	
		Spread();
	} while (next_permutation(idx.begin(),idx.end()));	 
	return;
}

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) {
				virusPos.push_back(make_pair(i, j));
				idx.push_back(0);
			}
			if (map[i][j] == 0)
				emptyPlace++;
		}
	}
	for (int i = 0; i < m; i++)  idx[i] = 1;
	sort(idx.begin(), idx.end());

	Simulation();
 
	if (time == 2500) cout << -1 << '\n';
	else cout << time << '\n';
	return 0;
}