[17142] 연구소 2

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

---

주어진 바이러스의 개수 중에서 M 개를 골라 바이러스를 퍼뜨려야 하기 때문에, 순열의 개념이 필요하고, 모든 연구소에 바이러스가 있게 하는 최소시간을 구해야 하기 때문에 BFS를 이용해서 푸는 문제입니다.

제가 이 문제를 풀 때 고민했던 첫번 째는 x와 y 좌표를 가진 Pair 클래스를 만들어 ArrayList 나 Queue에 넣어 사용하는데, 어떻게 순열로 뽑을까 하는 것이었습니다. 그래서 저는 2의 좌표가 들어있는 ArrayList 말고 따로 ArrayList를 선언해서 2의 좌표가 들어있는 ArrayList 만큼 0, 0의 좌표를 넣어 주었습니다. 그래서 ArrayList의 set 메소드로 2의 좌표를 순열로 뽑았습니다. 그리고 뽑힌 순열에서 BFS를 실시해서 연구소에 바이러스가 퍼지는 시간 minute 을 구했습니다. 

BFS 를 하는데 두번 째 문제가 생겼는데, 2의 개수가 5개일 때 3개를 뽑아서 최소시간을 구하는데 BFS를 하면서 나머지 2를 만났을 때 그것을 어떻게 체크하냐는 것이었습니다. 그래서 저는 똑같은 순열 두개를 뽑아서 하나는 최소시간을 구하는데 사용하고, 나머지 한개는 주어진 예제에서 2를 모두 없애고 2를 넣는데 사용하였습니다. 무슨 뜻이냐면 5개중에 2를 3개 고른다면 5개를 먼저 모두 없애고, 뽑힌 3개만 다시 2차원 배열에 넣어서 BFS를 실시 했습니다. 그러면 나머지 2의 영향을 받지 않고 주어진 좌표가 0인지 visited[][] 가 false인지만 판단해서 BFS를 할 수 있습니다.

마지막 문제는 minute을 구하고 바이러스가 연구소에 벽을 제외한 모든곳에 퍼졌는지 안퍼졌는지 판단하는 것이었는데, 제가 2번째 문제에서 처음에 주어진 2의 개수를 모두 없애고 뽑힌 순열의 2의 좌표만 넣었기 때문에, 나머지 안뽑힌 2의 좌표에 visited를 true로 최소시간을 구하고 마지막에 체크해주어서 바이러스가 연구소 전체에 퍼졌는지 안퍼졌는지 판단을 하여 퍼졌다면 minute을 ArrayList에 저장하고 그 중 최솟값을 출력했습니다.

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;

// 17142 연구소 2
public class Main {
	static int N, M, minute;
	static int [][] arr, map;
	static ArrayList<Pair> virus, list, check;
	static Queue<Pair> queue, que;
	static int [][] dir = {{1, 0},{0,1},{-1,0},{0,-1}};
	static boolean [][] visited;
	static ArrayList<Integer> result = new ArrayList<Integer>();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		arr = new int[N][N];
		virus = new ArrayList<Pair>();
		list = new ArrayList<Pair>();
		check = new ArrayList<Pair>();
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				arr[i][j] = sc.nextInt();
				if(arr[i][j] == 2) {
					virus.add(new Pair(i,j));
					check.add(new Pair(i,j));
				}
			}
		}
		
		for(int i=0; i<virus.size(); i++) {
			list.add(new Pair(0,0));
		}
		
		recur(0, 0);
		
		if(result.isEmpty()) System.out.println("-1");
		else {
			int min = 987987987;
			for(int i=0; i<result.size(); i++) {
				min = Math.min(result.get(i), min);
			}
			System.out.println(min);
		}
		
	}
	
	public static void recur(int start, int depth) {
		if(depth == M) {
			queue = new LinkedList<Pair>();
			que = new LinkedList<Pair>();
			map = new int[N][N];
			minute = -1;
			visited = new boolean[N][N];
			
			copy();
			
			for(int i=0; i<M; i++) {
				queue.add(list.get(i));
				que.add(list.get(i));
				check.add(list.get(i));
			}
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(map[i][j] == 2) {
						map[i][j] = 0;
					}
				}
			}
			
			while(!que.isEmpty()) {
				Pair p = que.poll();
				map[p.x][p.y] = 2; 
			}
			
			BFS();
			
			for(int i=0; i<check.size(); i++) {
				Pair p = check.get(i);
				visited[p.x][p.y] = true;
			}
			
			boolean flag = true;
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(map[i][j] != 1)
						if(visited[i][j] == false)
							flag = false;
				}
			}
			
			if(!flag) minute = -1;
			
			if(minute != -1) result.add(minute);
			
			return;
		}
		
		for(int i=start; i<virus.size(); i++) {
			list.set(depth, virus.get(i));
			recur(i+1, depth+1);
		}
	}
	
	public static void BFS() {
		
		while(!queue.isEmpty()) {
			int len = queue.size();
			
			for(int i=0; i<len; i++) {
				Pair p = queue.poll();
				visited[p.x][p.y]= true;
				
				for(int j=0; j<4; j++) {
					int nx = p.x+dir[j][0];
					int ny = p.y+dir[j][1];
					
					if(!isInside(nx, ny)) continue;
					
					if(map[nx][ny] == 0 && visited[nx][ny] == false) {
						visited[nx][ny] = true;
						queue.offer(new Pair(nx, ny));
					}
				}
			}
			minute++;
		}
	}
	
	public static boolean isInside(int x, int y) {
		if(x>=0 && x<N && y>=0 && y<N) return true;
		else return false;
	}
	
	public static void copy() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = arr[i][j];
			}
		}
	}
}

class Pair {
	int x, y;
	Pair(int x, int y){
		this.x=x;
		this.y=y;
	}
}