백준 17142 연구소3

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

문제링크

입력

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

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

출력

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

주안점

연구소는 사실 시리즈 문제다 1,2,3이 있고 이 문제가 마지막이다. 시리즈가 나아가면서 점점 제한 시간이 줄고 새로운 조건이 생긴다. 이 문제가 연구소2와 다른 점은 "활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다." 이 부분이다.
이 외에는 BFS+조합으로 풀 수 있지만 저 부분을 고려하지 않아서 3번정도 틀린 것 같다.

저 조건을 계속 읽어봐도 이해가 안 갔었는데 결국 이해한 바는 바이러스가 비활성 바이러스 칸에 가더라도 "빈칸"에 옮겨간 것이 아니므로 빈칸에 옮긴 시간만 체크해주면 된다는 것.

문제링크에서 예제1을 보면 (6,0)과 (6,6)으로 퍼지는 시간은 사실 고려할 필요가 없다. 그 이전에 빈칸에 모두 퍼질 수 있으므로.

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

public class Main {
    static int[][] map;
    static int N, M, zeroCount = 0;
    static List<int[]> candidate = new ArrayList<>();
    static boolean[] selected;
    static boolean[][] visited;
    static Queue<int[]> q;
    static int min = Integer.MAX_VALUE;
    static boolean cant = true;
    // 상 하 좌 우
    static final int[] mx = {0, 0, -1, 1};
    static final int[] my = {-1, 1, 0, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int val = Integer.parseInt(st.nextToken());
                map[i][j] = val;
                if (val == 2) candidate.add(new int[]{i, j});
                if (val == 0) zeroCount++;
            }
        }
        selected = new boolean[candidate.size()];
        backtracking(0, 0);
        if(cant) bw.write("-1\n");
        else bw.write(min + "\n");
        bw.flush();
        bw.close();
    }

    public static void backtracking(int now, int count) {
        int len = selected.length;
        if (count == M) {
            visited = new boolean[N][N];
            q = new LinkedList<>();
            for (int i = 0; i < len; i++) {
                if(selected[i]){
                    int[] cur = candidate.get(i);
                    visited[cur[0]][cur[1]] = true;
                    q.add(new int[]{cur[0], cur[1], 0});
                }
            }

            bfs();
            return;
        }
        for (int i = now; i < len; i++) {
            if(selected[i]) continue;
            selected[i] = true;
            backtracking(i, count + 1);
            selected[i] = false;
        }
    }

    public static void bfs() {
        int max = Integer.MIN_VALUE;
        int count = 0;
        while(!q.isEmpty()) {
            int[] cur = q.remove();

            for (int i = 0; i < 4; i++) {
                int ty = cur[0] + my[i];
                int tx = cur[1] + mx[i];

                if (ty >= 0 && ty < N && tx >= 0 && tx < N) {
                    if(map[ty][tx] != 1 && !visited[ty][tx]) {
                        visited[ty][tx] = true;
                        q.add(new int[]{ty, tx, cur[2] + 1});
                        if(map[ty][tx] == 0) {
                            count++;
                            max = Math.max(max, cur[2] + 1);
                        }
                    }
                }
            }
        }
        if(max == Integer.MIN_VALUE) max = 0;
        if(count == zeroCount) {
            cant = false;
            min = Math.min(max, min);
        }
    }
}