백준 17142번. 연구소 3 (Java)

Problem

• 문제 링크

연구소에는 벽과 비활성화된 바이러스가 있습니다.

10 개 이하의 비활성화 바이러스 중 M 개를 선택해서 활성화 시키려고 합니다.

활성화된 바이러스는 1 초에 인접한 상하좌우로 이동할 수 있으며 벽은 지나갈 수 없습니다.

M 개를 활성화시키는 모든 경우 중에서 바이러스가 연구소에 전부 퍼지는 최단시간을 구하는 문제입니다.

Solution

활성화된 바이러스를 택하는 모든 경우의 수는 백트래킹으로 구합니다.

Input 을 받을 때 바이러스들의 모든 리스트를 List<Virus> viruses 에 받아서 저장해둡니다.

재귀를 통해서 활성화 시킬 바이러스 리스트인 Virus[] active 를 구하고 나면 바이러스틀 퍼트립니다.

바이러스 퍼트리기는 BFS 로 진행하면 됩니다.

BFS 를 진행하면서 방문 체크가 필요한대, 기존 2차원 배열은 계속해서 사용해야되기 때문에 다른 배열을 복사하거나 생성해서 사용해야 합니다.

boolean[][] infected 배열을 통해 확산 여부를 체크하고 기존 배열로는 벽을 체크하면서 진행합니다.

처음 입력을 받을 때 미리 구해둔 emptySpace 를 사용해서 빈 공간의 갯수가 0 이 되는 순간의 시간초를 구하고 그 중 가장 작은 숫자를 구하면 됩니다.

주의할 점

1. 활성화된 바이러스가 퍼질 때 비활성화된 바이러스도 지나갈 수 있다.

2. 벽에 막혀서 바이러스가 존재하지 못하는 경우라고 반드시 -1 은 아니다. 다른 바이러스를 활성화 하면 성공할 수도 있다. 모든 바이러스의 경우를 만들었을때 전부 실패해야 -1 이다.

3. 바이러스를 퍼트릴 맵은 따로 복사해서 사용하는게 좋다.

4. 비활성화된 바이러스는 지나갈 수 있지만 도착하는 순간에 시간을 갱신하면 안된다. 비활성화된 바이러스들 때문에 바이러스가 전부 퍼졌는지 확인하는 건 빈 공간의 갯수로 파악하는 것이 훨씬 효과적이다.

Java Code

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

class Main {
    static class Virus {
        int x, y, time;

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

    static int N, M;
    static int[][] arr;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static List<Virus> viruses = new ArrayList<>();
    static Virus[] active;
    static int resultMinTime = Integer.MAX_VALUE;
    static int originEmptySpace = 0;

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

        // input
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        arr = new int[N][N];
        active = new Virus[M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());

                if (arr[i][j] == 0) {
                    originEmptySpace++;
                } else if (arr[i][j] == 2) {
                    viruses.add(new Virus(i, j, 0));
                }
            }
        }

        // solution
        if (originEmptySpace == 0) {
            System.out.println(0);
        } else {
            selectVirus(0, 0);
            System.out.println(resultMinTime == Integer.MAX_VALUE ? -1 : resultMinTime);
        }
    }

    // 백트래킹으로 M 개의 바이러스를 선택하는 Combination 구현
    static void selectVirus(int start, int selectCount) {
        if (selectCount == M) {
            spreadVirus(originEmptySpace);
            return;
        }

        for (int i = start; i < viruses.size(); i++) {
            active[selectCount] = viruses.get(i);
            selectVirus(i + 1, selectCount + 1);
        }
    }

    // BFS 로 바이러스를 퍼트린다
    static void spreadVirus(int emptySpace) {
        Queue<Virus> q = new LinkedList<>();
        boolean[][] infected = new boolean[N][N];

        for (int i = 0; i < M; i++) {
            Virus virus = active[i];
            infected[virus.x][virus.y] = true;
            q.add(virus);
        }

        while (!q.isEmpty()) {
            Virus virus = q.poll();

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

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

                if (arr[nx][ny] == 0) {
                    emptySpace--;
                }

                if (emptySpace == 0) {
                    resultMinTime = Math.min(resultMinTime, virus.time + 1);
                    return;
                }

                infected[nx][ny] = true;
                q.add(new Virus(nx, ny, virus.time + 1));
            }
        }
    }
}