[C/C++] 백준 - 17142번 (연구소3)

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

 

M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

 

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

 

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

입력

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

 

이 문제를 구현하는데에 있어 가장 헷갈렸던 부분은

"활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다."이다.

처음에 이 부분을 구현할 때 비활성 바이러스가 있는 칸으로 이동했을 때는 비활성 바이러스가 퍼지는 시간을 1로 하여 1이라는 시간으로부터 다시 퍼지는 시간을 계산하도록 하였다. 근데 이런식으로 구현하니 전에 퍼지는 시간을 모두 무시한채로 다시 1부터 시작 하는 방식으로 되어서 오답을 출력하기만 하였다.

 

시간이 증가되는 이동경로라는 것은 비활성 바이러스가 존재하지 않는 이동가능한 칸에 이동하였을 경우에만 시간이 늘어나야한다는 것을 예제7번을 보고 알았고, 이 부분을 다시 구현해주었다. 

 

바이러스를 고르는 것은 조합의 형식으로 구하면 되고, x,y좌표를 담는 구조체 형태의 배열로 저장한 후 큐에 넣는 방식으로 구현하였다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<cmath>
#include<iostream>
#include<vector>
#include<queue>
#define MAX_SIZE 50
#define INF 987654321

using namespace std;

// 바이러스는 활성상태와 비활성상태 존재
// 처음 모든 바이러스는 비활성
// 빈 칸, 벽, 바이러스로 존재
// 0 ; 빈칸, 1 ; 벽 , 2 ; 바이러스
struct node {
	int x;
	int y;
};

struct node ans[MAX_SIZE];
vector<pair<int, int>> v;
queue<pair<int, int>> q;

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

int N, M, zero_cnt;
int graph[MAX_SIZE][MAX_SIZE];
int copy_graph[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE][MAX_SIZE];
bool checked[MAX_SIZE];

int result = INF;
int rst;

void input() {
	zero_cnt = 0;
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &graph[i][j]);
			if (graph[i][j] == 2) {
				v.push_back({ i,j });
			}
			else if (graph[i][j] == 0) zero_cnt++;
		}
	}
}

void copy() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (graph[i][j] == 1)
				copy_graph[i][j] = -1;
			else if (graph[i][j] == 0)
				copy_graph[i][j] = 0;
			else
				copy_graph[i][j] = -7;
		}
	}
}

void bfs() {
	rst = 0;
	int nextX, nextY;
	int emptyplace = 0;
	while (!q.empty()) {
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			nextX = cur_x + dx[i];
			nextY = cur_y + dy[i];

			if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
			if (!visited[nextX][nextY]) {
				if (copy_graph[nextX][nextY] == 0 || copy_graph[nextX][nextY] == -7) {
					visited[nextX][nextY] = visited[cur_x][cur_y] + 1;
					if (copy_graph[nextX][nextY] == 0) {
						emptyplace++;
						rst = visited[nextX][nextY];
					}
					q.push({ nextX, nextY });
				}
			}
		}
	}
	if(zero_cnt == emptyplace) result = min(result, rst);
}

void func(int depth, int start) {
	if (depth == M) {
		copy();
		memset(visited, false, sizeof(visited));
		for (int i = 0; i < M; i++) {
			q.push({ ans[i].x, ans[i].y });
			visited[ans[i].x][ans[i].y] = 1;
			copy_graph[ans[i].x][ans[i].y] = 1;
		}
		bfs();
		return;
	}

	for (int i = start; i < v.size(); i++) {
		if (!checked[i]) {
			checked[i] = true;
			ans[depth].x = v.at(i).first;
			ans[depth].y = v.at(i).second;
			func(depth + 1, i+1);
			checked[i] = false;
		}
	}
}

void solve() {
	func(0,0);
	if (result != INF)
		printf("%d\n", result-1);
	else
		printf("-1\n");
}

int main() {
	input();
	if (zero_cnt == 0) {
		printf("0");
		return 0;
	}
	solve();

	return 0;
}