[백준 JAVA] 17142 : 연구소 3

[백준 17142] 연구소 3 : https://www.acmicpc.net/problem/17142

---

문제 조건 정리

 

1. 바이러스는 활성 상태와 비활성 상태가 있다.
   가장 처음에 모든 바이러스는 비활성 상태이고,
   활성 상태인 바이러스는 상하좌우로 인접한 모든 빈칸으로 동시에 복제되며, 1초가 걸린다.
   승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.
   
   
2. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며,
   정사각형은 1 ×1 크기의 정사각형으로 나누어져 있다.
   연구소는 빈칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
   활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다. -> 비활성 바이러스는 빈칸으로 취급
   
   
3. 0은 빈칸, 1은 벽, 2는 바이러스의 위치이다.
   
   
4. 연구소의 상태가 주어졌을 때, 모든 빈칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

---

입력

 

1. 첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50),
   놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)
   
   
2. 둘째 줄부터 N개의 줄에 연구소의 상태
   0은 빈 칸, 1은 벽, 2는 비활성 바이러스의 위치
   2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수

---

문제를 풀기 전

 

1. 백트래킹으로 활성 바이러스 M개 선택하고 BFS 해야겠다.
   
   
2. 탐색 가능한 범위를 모두 탐색한 것을 어떻게 확인할까...
   입력받을 때, 빈 공간을 미리 확인하자.
   그리고 BFS 과정에서 빈 공간에 모두 진입했는지 체크하자. 못하면 최솟값 갱신하지 않는 걸로.
   
   
3. 최악의 시간복잡도는 10C5 * 50^2 = 대략 60만이므로 제한 시간 내로 풀 수 있을 것으로 예상함.

---

코드

 

package baekJoon;

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

public class BJ17142 {

    // 큐에서 사용할 바이러스의 이동 상태를 정의
    private static class State {
        int x, y, time;

        public State(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }

    static int n, m;
    static List<int[]> viruses = new ArrayList<>();
    static int[][] map;
    static int initialEmptySpace = 0;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int minTime = Integer.MAX_VALUE;


    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()); // 초기 활성 바이러스 개수

        map = new int[n][n]; // 복사를 위한 원본 배열

        for (int i = 0; i < n; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(stringTokenizer.nextToken());
                if (map[i][j] == 0) {
                    initialEmptySpace++; // 빈칸 개수
                }
                if (map[i][j] == 2) {
                    viruses.add(new int[]{i, j}); // 바이러스 위치 저장
                }
            }
        }

        // 빈칸이 0개라면 즉시 종료
        if (initialEmptySpace == 0) {
            System.out.println(0);
            return;
        }


        simulate(0, 0, new int[m]);

        System.out.println(minTime == Integer.MAX_VALUE ? -1 : minTime);

    }

    // depth -> 활성 바이러스 선택 개수
    // start -> activeVirusIdx를 선택하는 시작 인덱스
    // activeVirusIdx -> 선택된 활성 바이러스 인덱스
    private static void simulate(int depth, int start, int[] activeVirusIdx) {
        // 활성 바이러스를 m개 골랐다면
        if (depth == m) {
            // 바이러스 퍼뜨리기
            spreadVirus(activeVirusIdx);
            return;
        }

        // 활성 바이러스 고르기 start ~ (virus.size - 1)
        for (int i = start; i < viruses.size(); i++) {
            activeVirusIdx[depth] = i;
            simulate(depth + 1, i + 1, activeVirusIdx);
        }

    }

    private static void spreadVirus(int[] activeVirusIdx) {
        Queue<State> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[n][n];

        // 선택된 활성 바이러스를 큐에 삽입
        for (int idx : activeVirusIdx) {
            int virusX = viruses.get(idx)[0];
            int virusY = viruses.get(idx)[1];
            visited[virusX][virusY] = true;
            queue.offer(new State(virusX, virusY, 1));
        }

        int currMaxTime = 0; // 현재 BFS에 소모된 시간
        int visitCount = 0; // 현재 BFS에서 빈칸에 방문한 횟수

        // 큐가 비어있지 않고, 모든 빈칸에 방문하지 않았다면
        while (!queue.isEmpty() && visitCount != initialEmptySpace) {
            State curr = queue.poll();
            currMaxTime = Math.max(currMaxTime, curr.time);

            for (int d = 0; d < 4; d++) {
                int nextX = curr.x + dx[d];
                int nextY = curr.y + dy[d];

                if (isSafe(nextX, nextY) && !visited[nextX][nextY] && map[nextX][nextY] != 1) {
                    visited[nextX][nextY] = true;
                    queue.offer(new State(nextX, nextY, curr.time + 1));
                    if (map[nextX][nextY] == 0) visitCount++;
                }
            }
        }

        // 방문 횟수가 빈칸 개수와 같다면 정답(최소 시간)을 갱신
        if (visitCount == initialEmptySpace) {
            minTime = Math.min(minTime, currMaxTime);
        }

    }

    private static boolean isSafe(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < n;
    }

}

 

---

문제를 풀고 난 후

 

모든 빈칸에 방문했는지 체크해야 하는 조건을 효율적으로 해결하기 위해서 생각을 많이 했다.

정직한 BFS, 완전 탐색 문제라서 좋았다.