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

 

해결방법 > 

DFS(깊이우선탐색)과 BFS(너비우선탐색)을 사용해서 해결할 수 있는 문제이다.

 

두 가지 과정이 필요하다.

 

1) DFS로 활성화할 m개의 바이러스를 선택한다.

 

2) BFS로 선택된 m개의 바이러스를 이동거리중 가장 긴 경로를 찾는다.

 

단, 한 가지 고려해야할 점은 빈 칸에 바이러스를 확산시키는 시간을 찾는 문제이기 때문에

 

앞으로 탐색할 노드가 비활성화 바이러스만 남아있다면 탐색을 종료한다.

 

예로 예제 7번이 있다.

 

[JAVA]

package baekjoon;

import java.util.*;
import java.io.*;

public class BOJ_17142 {
	static int[][] map;
	static ArrayList <Node> virus = new ArrayList<>();
	static int n;
	static int m;
	static int min = -1;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	public static class Node{
		int x;
		int y;
		
		Node(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
	public static void insfect(int[] s) {
		Queue <Node> q = new LinkedList<>();
		int[][] n_map = new int[n][n];
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				n_map[i][j] = map[i][j];
			}
		}
		
		for(int i = 0; i < s.length; i++) {
			if(s[i] == 0)
				n_map[virus.get(i).x][virus.get(i).y] = -1;
		}
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(n_map[i][j] == 2) {
					q.add(new Node(i, j));
				}
			}
		}
		
		while(!q.isEmpty()) {
			int zero = 0;
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(n_map[i][j] == 0) {
						zero = 1;
						break;
					}
				}
			}
			if(zero == 0) break;
			
			Node node = q.poll();
			int x = node.x;
			int y = node.y;
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(nx >= 0 && ny >= 0 && nx < n && ny < n && (n_map[nx][ny] == 0 || n_map[nx][ny] == -1)) {
					q.add(new Node(nx, ny));
					n_map[nx][ny] = n_map[x][y] + 1;
				}
			}
		}
		
		int flag = 0;
		int max = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(n_map[i][j] == 0) {
					flag = 1;
					break;
				}
				max = Math.max(n_map[i][j], max);
			}
		}
		
		if(flag == 0) {
			if(min == -1) min = max - 2;
			else min = Math.min(max - 2, min);
		}
	}
	
	public static void activate(int v, int flag, int depth, int[] s) {
		if(v >= s.length) return;
		int[] selected = s.clone();
		selected[v] = flag;
		if(depth == m) {
			insfect(selected);
			return;
		}
		activate(v + 1, 0, depth, selected);
		activate(v + 1, 1, depth + 1, selected);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk = new StringTokenizer(br.readLine());
		n = Integer.parseInt(tk.nextToken());
		m = Integer.parseInt(tk.nextToken());
		map = new int[n][n];
		
		for(int i = 0; i < n; i++) {
			tk = new StringTokenizer(br.readLine());
			for(int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(tk.nextToken());
				if(map[i][j] == 2) virus.add(new Node(i, j));
			}
		}
		
		
		int[] selected = new int[virus.size()];
		activate(0, 0, 0, selected);
		activate(0, 1, 1, selected);
		
		System.out.println(min);
	}
}