[BOJ] 17141 연구소 2(Java)

문제

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

17141번: 연구소 2

풀이

- 입력 시 2(바이러스)인 좌표를 VIRUSES에 추가하고, 1(벽)이 아닌 값(바이러스가 퍼질 수 있는 공간)의 개수를 센다.

- 최소 시간을 n*n로 초기화 하고, 퍼트릴 바이러스 m개를 조합을 이용해 선택한다.

- 선택된 바이러스를 Queue에 추가하고 BFS를 이용해 바이러스를 퍼뜨리며 퍼뜨린 시간으로 최소 시간을 갱신한다.

    - 빈 공간(empty)를 '바이러스가 퍼질 수 있는 공간 - 퍼뜨릴 바이러스 개수'로 초기화하고, 바이러스가 퍼질 때마다 감소시킨다.

    - 연구소 탐색 종료 후 빈 공간이 0이면 바이러스가 연구소에 전체에 퍼진 것이므로 최소 시간을 갱신한다.

- 최소 시간이 n*n이면 바이러스가 연구소 전체에 퍼질 수 없음을 뜻하므로 -1을 출력하고, 그렇지 않으면 최소 시간을 출력한다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static final int[][] DELTAS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private static final List<int[]> VIRUSES = new ArrayList<>();
    private static final Queue<int[]> SPREAD_VIRUSES = new ArrayDeque<>();
    private static final int WALL = 1;
    private static final int VIRUS = 2;

    private static int[][] laboratory;
    private static int[] selected;
    private static boolean[][] isVisited;
    private static int n;
    private static int m;
    private static int spreadableSpace;
    private static int minTime;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        n = Integer.parseInt(stringTokenizer.nextToken());
        m = Integer.parseInt(stringTokenizer.nextToken());
        laboratory = new int[n][n];
        isVisited = new boolean[n][n];
        selected = new int[m];
        for (int i = 0; i < n; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int j = 0; j < n; j++) {
                int input = Integer.parseInt(stringTokenizer.nextToken());
                laboratory[i][j] = input;
                if (input == VIRUS) {
                    VIRUSES.add(new int[]{i, j});
                }
                if (input != WALL) {
                    spreadableSpace++;
                }
            }
        }
        minTime = n * n;
        selectVirus(0, 0);
        if (minTime == n * n) {
            System.out.println(-1);
        } else {
            System.out.println(minTime);
        }
    }

    private static void selectVirus(int cnt, int start) {
        if (cnt == m) {
            for (int i = 0; i < n; i++) {
                Arrays.fill(isVisited[i], false);
            }
            for (int selectedVirus : selected) {
                int[] virus = VIRUSES.get(selectedVirus);
                SPREAD_VIRUSES.offer(virus);
                isVisited[virus[0]][virus[1]] = true;
            }
            spreadVirus();
            return;
        }

        for (int i = start, size = VIRUSES.size(); i < size; i++) {
            selected[cnt] = i;
            selectVirus(cnt + 1, i + 1);
        }
    }

    private static void spreadVirus() {
        int empty = spreadableSpace - m;
        int time = -1;
        while (!SPREAD_VIRUSES.isEmpty()) {
            time++;
            int size = SPREAD_VIRUSES.size();
            while (size-- > 0) {
                int[] current = SPREAD_VIRUSES.poll();
                int x = current[0];
                int y = current[1];
                for (int[] delta : DELTAS) {
                    int dx = x + delta[0];
                    int dy = y + delta[1];
                    if (dx >= 0 && dx < n && dy >= 0 && dy < n && !isVisited[dx][dy] && laboratory[dx][dy] != WALL) {
                        empty--;
                        isVisited[dx][dy] = true;
                        SPREAD_VIRUSES.offer(new int[]{dx, dy});
                    }
                }
            }
        }
        if (empty == 0) {
            minTime = Math.min(minTime, time);
        }
    }
}