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

 

생각

브루트 포스를 이용해 M개의 활성 바이러스가 최소의 시간에 모두 퍼트릴 수 있는 방법을 찾아야 한다. 모든 경우에 대해 파악해야 하므로 처음에 받은 map을 그대로 사용하는게 아니라 deep copy를 이용해 복사된 배열을 사용하는게 편할 것이다.

 

과정은 다음과 같다.

 

1. 조합을 이용해 바이러스가 있는 것 중 M를 활성 바이러스로 변경한다.

2. 1초 마다 활성바이러스를 퍼트리며 연구소에 퍼트린다. (이 때, 3으로 활성화 된 바이러스가 2를 만났을 때 이를 3으로 바꿔주는게 중요하다!! - 실수하기 쉽다.)

3. 더 이상 바이러스가 퍼질 수 없으면 종료한다.

4. 바이러스가 퍼지지 않은 곳이 있는지 체크하고, 있다면 -1을 출력 없다면 걸린 시간을 출력해준다.

 

또한 next_permutation()을 구현해서 조합을 만들었는데, 재귀를 사용하는 방법도 있지만 이렇게 되면 숫자가 커지면 함수 호출 수가 많아져 스택 오버플로우가 날 수 있으므로 next_permutation을 사용하는 것도 추천한다. (외우기 강추)

주석으로 설명을 더 적도록 하겠다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    //n:연구소 크기, m: 바이러스 개수
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    static int n,m;
    static int[][] map;
    static int time = 0;
    static ArrayList<dot> virus_first = new ArrayList<dot>();
    static int[] comb;
    static Queue<dot> virus_wake = new LinkedList<dot>();
    static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        
        map = new int[n][n];
        
        for(int i=0; i<n; i++) {
            str = br.readLine().split(" ");
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(str[j]);
                
                if(map[i][j] == 2) {
                    virus_first.add(new dot(i,j));
                }
            }
        }
        
        comb = new int[virus_first.size()];
        //next_permutataion을 조합처럼 사용하기 위해 0과 1로 나누어진 배열을 만들었다.
        for(int i=0; i<comb.length; i++) {
            if(i<m) {
                comb[i] = 0;
            } else {
                comb[i] = 1;
            }
        }
        
        //next_permutatoin은 do-while을 사용해야 한다.
        do {
            int[][] map_copy = new int[n][n];
            virus_wake = new LinkedList<dot>();
            
            for(int i=0; i<n; i++) {
                map_copy[i] = Arrays.copyOf(map[i], n);
            }
            
            for(int i=0; i<comb.length; i++) {
                if(comb[i] == 0) {
                    virus_wake.add(virus_first.get(i));
                    map_copy[virus_first.get(i).x][virus_first.get(i).y] = 3;
                }
            }
            //큐에 활성화 바이러스가 존재하지 않을 때, 또는 이미 모든 바이러스가 퍼지면 종료한다.
            while(true) {                
                if(virus_wake.size() == 0 || check(map_copy)) {
                    break;
                }
                
                bfs(map_copy);
                time++;
            }
            
            if(min > time && check(map_copy)) {
                min = time;
            }
            time = 0;
            
        } while(next_permutation(comb));
        
        if(min == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {        
            System.out.println(min);
        }
    }
    
    //단순 bfs
    public static void bfs(int[][] map_copy) {
        int size = virus_wake.size();
        
        for(int i=0; i<size; i++) {
            dot d = virus_wake.poll();
            int x = d.x;
            int y = d.y;
            
            for(int j=0; j<4; j++) {
                int x2 = x + dx[j];
                int y2 = y + dy[j];
                
                if(x2>=0 && x2<n && y2>=0 && y2<n && (map_copy[x2][y2] == 0 || map_copy[x2][y2] == 2)) {
                    map_copy[x2][y2] = 3;
                    virus_wake.add(new dot(x2,y2));
                }
             }
        }    
    }
    //증가하는 가장 긴 접미사 수열을 구해 인덱스로 이렇게 저렇게 해서 순열을 만드는 것.
    public static boolean next_permutation(int[] arr) {
        int i = arr.length-1;
        
        while(i>0 && arr[i-1] >= arr[i]) {
            i--;
        }
        
        if(i<=0) {
            return false;
        }
        
        int j = arr.length-1;
        
        while(arr[i-1] >= arr[j]) {
            j--;
        }
        
        int temp = arr[i-1];
        arr[i-1] = arr[j];
        arr[j] = temp;
        
        j = arr.length-1;
        
        while(i < j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
        return true;
        
    }
    
    public static boolean check(int[][] map) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(map[i][j] == 0) {
                    return false;
                }
            }
        }
        
        return true;
    }
}
 
class dot {
    int x;
    int y;
    
    public dot(int x,int y) {
        this.x = x;
        this.y = y;
    }
}