[백준] 17142 - 연구소 3

문제

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

 

예제 입력

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

예제 출력

4

 

풀이 방법

1. 바이러스가 있는 곳(map[y][x]가 2인 곳)을 리스트에 담은 후 그 리스트에서 M개를 선택하는 조합을 이용했다.

   빈칸(map[y][x]가 0인 곳)의 개수를 noneCnt변수에 저장했다.

   이유: 위 예제처럼 마지막에 비활성바이러스가 남아있고 다른 빈칸에 모두 바이러스가 퍼졌을때

   더 이상 바이러스가 퍼지지 않아도 이미 모든 칸에 바이러스가 퍼진 경우이므로 더이상 연산을 안해도 된다.

 

2. 선택한 M개의 좌표를 Queue에 넣고 bfs로 진행했다.

    M개를 선택할 때마다 계산을 해주어야 하기 때문에 bfs연산 시 noneCnt변수를 매개변수 none으로 넘겨주었다.

 

3. 큐에서 꺼낸 좌표의 값이 0이라면 none변수를 1개씩 감소한다.

 

4. 바이러스가 모두 퍼진 경우(none이 0이 된경우) 중 가장 시간이 적게 걸린 경우를 출력

 

 

내 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_17142 {
	static int N, M, noneCnt=0, min=Integer.MAX_VALUE;
	static int[][] map;
	
	static class Virus{
		int y, x, depth;

		public Virus(int y, int x, int depth) {
			super();
			this.y = y;
			this.x = x;
			this.depth = depth;
		}
	}
	
	static List<Point> virusList = new ArrayList<>();
	static Point[] activated;
	
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		activated = new Point[M];
		
		for (int y = 0; y < N; y++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int x = 0; x < N; x++) {
				map[y][x] = Integer.parseInt(st.nextToken());
				if(map[y][x] == 2) virusList.add(new Point(x, y));
				else if(map[y][x] == 0) noneCnt++;
			}
		}
		
		combi(0, 0);
		if(min == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(min);
		
		br.close();

	}

	private static void combi(int cnt, int start) {
		if(cnt == M) {
			bfs(activated, new boolean[N][N], noneCnt);
			return;
		}
		
		for (int i = start; i < virusList.size(); i++) {
			activated[cnt] = virusList.get(i);
			combi(cnt+1, i+1);
		}
	}

	private static void bfs(Point[] act, boolean[][] visited, int none) {
		Queue<Virus> queue = new LinkedList<>();
		for (int i = 0; i < act.length; i++) {
			queue.offer(new Virus(act[i].y,act[i].x,0));
			visited[act[i].y][act[i].x] = true;
		}
		
		while(!queue.isEmpty()) {
			Virus cur = queue.poll();
			
			if(map[cur.y][cur.x]==0) none--;
			if(none==0) {
				min = Math.min(min, cur.depth);
				return;
			}
			
			for (int d = 0; d < 4; d++) {
				int ny = cur.y + dy[d];
				int nx = cur.x + dx[d];
				
				if(ny<0 || ny>=N || nx<0 || nx>=N) continue;
				if(visited[ny][nx] || map[ny][nx]==1) continue;
				
				queue.offer(new Virus(ny, nx, cur.depth+1));
				visited[ny][nx] = true;
			}
		}
	}
}