[백준/JAVA] BOJ 17141 - 연구소 2

조합 + bfs 은 재미지다

👀 문제

17141번: 연구소 2 ✨ 골드 4

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×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 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 5

시간이 최소가 되는 방법은 아래와 같고, 5초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

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
5 - 3 2 3 4 5

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

예제 입력

7 3
2 0 2 0 1 1 0
0 0 1 0 1 2 0
0 1 1 2 1 0 0
2 1 0 0 0 0 2
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 2 0 2

예제 출력

5

🔑 키포인트

조합 너비 우선 탐색

✍️ 코드

📍 바이러스를 놓는 조합을 구한 뒤, bfs를 이용해 시간을 구하면 되는 문제

🤔 static이 뭐 이리 많냐... (그치만 매개변수로 주기 싫단 말이에요)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ17141_연구소2 {
    static int n, m, answer;
    static int[][] map;
    static boolean[][] visited;
    static ArrayList<int[]> virus;
    static ArrayList<int[]> combArr;
    static Queue<Node> q;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };

    static class Node {
        int x, y, time;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][n];
        virus = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 2) {
                    virus.add(new int[] { i, j });
                }
            }
        }
        answer = Integer.MAX_VALUE;
        combArr = new ArrayList<>();
        comb(0, 0); // 바이러스 놓기

        // 다 퍼지는 게 불가능한 경우는 -1 반환
        if (answer != Integer.MAX_VALUE) {
            System.out.println(answer);
        } else {
            System.out.println(-1);
        }
    }

    // 바이러스 놓을 수 있는 위치 조합 구하기
    static void comb(int idx, int depth) {
        if (depth == m) {
            // 다 퍼지는 데에 얼마나 걸리는지 계산하기
            answer = Math.min(answer, time());
            return;
        }
        for (int i = idx; i < virus.size(); i++) {
            combArr.add(virus.get(i));
            comb(i + 1, depth + 1);
            combArr.remove(combArr.size() - 1);
        }
    }

    static int time() {
        int time = 0;
        visited = new boolean[n][n];
        q = new LinkedList<>();
        for (int[] v : combArr) {
            q.offer(new Node(v[0], v[1], 0));
            visited[v[0]][v[1]] = true;
        }

        while (!q.isEmpty()) {
            Node now = q.poll();
            time = now.time;

            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (!visited[nx][ny] && map[nx][ny] != 1) {
                        visited[nx][ny] = true;
                        q.offer(new Node(nx, ny, now.time + 1));
                    }
                }
            }
        }

        // 바이러스 다 퍼졌으면 시간을, 아니라면 MAX_VALUE 반환
        if (isValid()) {
            return time;
        } else {
            return Integer.MAX_VALUE;
        }
    }

    // 바이러스가 다 퍼졌는지 확인
    static boolean isValid() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] != 1 && !visited[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}