17141 - 연구소(G4)

문제

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

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×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 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 5

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

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
5 - 3 2 3 4 5

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

입력

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

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

출력

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

풀이

바이러스가 퍼질 수 있는 위치를 조합을 통해 선택하였다.
이로써 모든 경우의 수를 고려할 수 있게 된다. 선택된 위치를 큐에 넣고 BFS를 실행한다.

여기서 고민했던 점이 있었다.
바로 간단한 BFS에서는 큐에 들어가는 인자에 시간값을 넣었었는데 여기서는 그렇게 하기 힘들다는 점.

여러 개의 인자를 큐에 넣다보니 시간 고려에 애로사항이 있었다. 이를 위해 큐의 사이즈를 미리 잰 뒤, 사이즈만큼 BFS를 실행하고 다음 인자부터는 시간을 늘리는 방법을 사용했다.

코드

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

public class Main {
	static int N, M, res = Integer.MAX_VALUE;
	static int[][] map;
	static List<virus> virusList = new ArrayList<>(); //바이러스 담을 리스트
	static int[] pick;
	
	static int[][] d = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
	static Queue<virus> q = new ArrayDeque<>();
	static boolean visit[][];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		//맵 입력받기
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();

				if(map[i][j] == 2) { 				//바이러스 위치 저장
					virusList.add(new virus(i, j));
				}
			}
		}
		
		//조합으로 바이러스 위치 찾기
		pick = new int[M]; //골라진 바이러스들 인덱스 담을 배열
		comb(0, 0);
		
		//결과 출력
		if(res == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(res);
	}
	private static void comb(int start, int cnt) {
		if(cnt == M) {
			solve();
			return;
		}
		
		for (int i = start; i < virusList.size(); i++) {
			pick[cnt] = i;
			comb(i + 1, cnt + 1);
		}
	}

	private static void solve() {
		visit = new boolean[N][N];
		//조합으로 고른 바이러스들 큐에 삽입
		for (int i = 0; i < M; i++) {
			virus v = virusList.get(pick[i]);
			q.offer(v);
			visit[v.r][v.c] = true;	
		}
		
		//BFS
		int nowTime = -1; 
		while(!q.isEmpty()) {
			
			int size = q.size(); //현재 큐의 사이즈 저장
			while(size-- > 0) {  //저장된 사이즈만큼 큐를 늘리고, 시간을 1초 추가
				virus v = q.poll();
				int r = v.r;
				int c = v.c;
						
				for (int i = 0; i < d.length; i++) {
					int nr = r + d[i][0];
					int nc = c + d[i][1];
					
					if(cantGo(nr, nc)) continue;
					if(map[nr][nc] == 1 || visit[nr][nc]) continue;
					q.offer(new virus(nr, nc));
					visit[nr][nc] = true;
					
				}
			}
			nowTime += 1;
		}
		
		//값이 존재할 경우 최저기록과 비교
		if(check()) res = Math.min(res, nowTime);
	}
	
	private static boolean check() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(map[i][j] == 0 && !visit[i][j]) return false;
			}
		}
		return true;
	}
	static boolean cantGo(int r, int c) {
		if(r < 0 || c < 0 || r >= N || c >= N) return true;
		return false;
	}
	
	static class virus {
		int r, c;

		public virus(int r, int c) {
			super();
			this.r = r;
			this.c = c;
			
		}
	}
}