[백준 Baekjoon] 17142번 연구소 3 - JAVA

[백준 Baekjoon] 17142번 연구소 3 - JAVA

---

 

문제 풀이

시간 제한이 0.25초라는 말에 조금 겁을 먹었던 문제이었습니다. 문제를 읽어보면서 저 짧은 시간안에 어떻게 풀어야할지 고민을 많이 했었는데, M개의 바이러스를 선택해 그래프 탐색으로 검사하는 방법밖에 생각나지 않았고, 맞는 방법이라 생각했습니다.

 

우선 입력을 받으면서 빈 칸의 수(emptySpace), 바이러스의 위치(list)를 저장해야 합니다.

 

혹시나 제출하시고 92%에서 틀린다면 빈 칸의 수가 0인 경우를 검사하지 않았기 때문일 것입니다.

제가 작성한 방법에서도 빈 칸이 있다고 가정하고 확산을 하여 무조건 1이상이 나옵니다.

 

전체 바이러스에서 M개의 바이러스를 선택해서 확산을 시키고 검사해야 합니다.

조합을 사용하여 M개의 바이러스를 선택할 수 있는 경우를 전부 검사합니다.

 

선택한 바이러스를 큐로 옮기고 그래프 탐색을 사용하여 바이러스 확산 시뮬레이션을 수행합니다.

탐색을 하며 빈 칸인지 확인하고 빈 칸의 수(emptySpace)를 감소 시킵니다. 비활성화 된 바이러스도 탐색이 가능하기 때문입니다.

한 번 큐에 있는 모든 바이러스의 확산이 완료되면 시간(time)이 증가합니다.

 

빈 칸이 더 이상 존재 하지 않는 경우 최소 시간을 갱신합니다.

만약 현재 최소 시간 보다 오래 걸린다면 더이상 검사할 필요가 없어 종료합니다.

 

소스 코드

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

public class Main {
    public static int N, M, emptySpace, answer = Integer.MAX_VALUE;
    public static int[][] map;

    public static List<Virus> list = new ArrayList<>();
    public static Virus[] activeVirus;

    public static int[] dx = {1, 0, -1, 0};
    public static int[] dy = {0, 1, 0, -1};

    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];
        activeVirus = new Virus[M];

        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] == 0) {
                    emptySpace++;
                } else if (map[i][j] == 2) {
                    list.add(new Virus(i, j));
                }
            }
        }

        if (emptySpace == 0) { // 빈 칸이 없는 경우
            System.out.println(0);
            return;
        }

        combination(0, 0);

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

    // 조합을 사용하여 M개의 바이러스를 선택할 수 있는 경우를 전부 검사
    public static void combination(int depth, int start) {
        if (depth == M) {
            spread(emptySpace);
            return;
        }

        for (int i = start; i < list.size(); i++) {
            activeVirus[depth] = list.get(i);
            combination(depth + 1, i + 1);
        }
    }

    // 바이러스 확산
    public static void spread(int emptySpace) {
        Queue<Virus> queue = new LinkedList<>();
        boolean[][] visit = new boolean[N][N];

        for (Virus v : activeVirus) {
            queue.add(v);
            visit[v.x][v.y] = true;
        }

        int time = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                Virus cur = queue.poll();

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

                    if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                    if (visit[nx][ny] || map[nx][ny] == 1) continue;

                    // 탐색을 하며 빈 칸인지 확인하고 빈 칸의 수(emptySpace)를 감소
                    if (map[nx][ny] == 0) {
                        emptySpace--;
                    }

                    queue.add(new Virus(nx, ny));
                    visit[nx][ny] = true;
                }
            }

            // 한 번 큐에 있는 모든 바이러스의 확산이 완료되면 시간(time)이 증가
            time++;

            // 만약 현재 최소 시간 보다 오래 걸린다면 더이상 검사할 필요가 없어 종료
            if (time >= answer) {
                return;
            }

            // 빈 칸이 더 이상 존재 하지 않는 경우 최소 시간을 갱신
            if (emptySpace <= 0) {
                answer = time;
            }
        }
    }

    public static class Virus {
        int x;
        int y;

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