[백준/c++] 17142 연구소 3

문제

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

구현해야할 조건

활성과 비활성 상태의 바이러스를 고르는 방식은 바이러스의 크기가 10개 이하이기 때문에, 충분히 next_permutation으로 구할 수 있을 것으로 보고 직접 조합을 구현하지는 않았다. 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며,1초가 걸리게 되고, 연구소의 바이러스 M개를 바꾸면 되는데 가장 문제를 이해하면서 부족했던 점은 "활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다"에서 그럼 활성으로 변하니까 바로 전염을 시키는 건지 빈칸에 바이러스를 옮긴 것 처럼 옮겨가는 것인지? 그것이 이해가 안갔는데, 딱히 반례가 존재하는 것도 아니고 문제 예시를 보아도 그냥 무시하고 진행하기 때문에 무시하고 진해해도 상관이 없을 것 같다! 비활성화 바이러스도 자리를 차지하고 있는 것으로 나오기 때문에!
재채점이 되면 저부분이 추가되어 되려나? 

code

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

#define MAX 51
#define INF 987654321
using namespace std;

const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0}; 

int n,m,cnt = 0;
int result = INF;
int board[MAX][MAX];
vector<pair<int,int> > virus;
vector<bool> visited;

bool chk = false;

void DFS(int cnt)
{
	
	int copyBoard[MAX][MAX];
	
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			copyBoard[i][j] = board[i][j]; // 복사해주고 

	
	queue<pair<int,int> > q; // 4방향 이동을 해야하기 때문에 
	
	for(int i = 0; i < visited.size(); i++)
	{
		if(visited[i])
		{
			q.push({virus[i].first, virus[i].second});
			copyBoard[virus[i].first][virus[i].second] = 3;
		}
	}
	
	int time = 0;
	
	while(!q.empty())
	{
		int size = q.size();
		
		if(!cnt)
		{
			chk = true;
			result = min(result, time);
			break;
		}
		
		time++;
		
		for(int i = 0; i < size; i++)
		{
			int y = q.front().first;
			int x = q.front().second;
			
			q.pop();
			
			for(int i = 0; i < 4; i++)
			{
				int ny = y + dy[i];
				int nx = x + dx[i];
				
				if(0 <= nx && nx < n && 0 <= ny && ny < n)
				{
					if(!copyBoard[ny][nx] || copyBoard[ny][nx] == 2)
					{
						if(!copyBoard[ny][nx])
							cnt--;
						
						copyBoard[ny][nx] = 3;
						q.push({ny,nx});
					}
				}
			}
		}
	}
	
	return;
}


int main()
{
	cin >> n >> m;
	
	// 0은 빈칸, 1은 벽, 2는 바이러스 위치 
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			cin >> board[i][j];
			
			if(board[i][j] == 2)
				virus.push_back({i,j}); // virus location
			else if(board[i][j] == 0) // 감염이 아직 안된 순수 지역 
				cnt++;
		}
	}
	
	sort(virus.begin(), virus.end());
	visited.resize(virus.size());
	
	for(int i = 0; i < visited.size(); i++)
		visited[i] = 0;
		
	for(int i = 0; i < m; i++)
		visited[i] = 1;
		
	sort(visited.begin(), visited.end()); // virus의 위치랑 맞춰주기 위한 작업
	
	do{
		
		DFS(cnt); // cnt 바이러스로 감염시켜야 할 갯수 
		
	}while(next_permutation(visited.begin(), visited.end()));
	
	if(chk)
		cout << result;
	else
		cout << -1;
	
	return 0;
}