[백준] 17142번. 연구소 3(JAVA)

문제

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

---

풀이(25분)

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

public 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 final int EMPTY = 0;
    static final int WALL = 1;
    static final int VIRUS = 2;

    static int N, M;
    static int[][] lab;
    static List<Virus> virusCandidates = new ArrayList<>();
    static Virus[] activeViruses;
    static int minTime = Integer.MAX_VALUE;
    static int totalEmptyCells = 0;

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

    public static void main(String[] args) throws IOException {
        initInput();
        if (totalEmptyCells == 0) {
            System.out.println(0);
        } else {
            chooseViruses(0, 0);
            System.out.println(minTime == Integer.MAX_VALUE ? -1 : minTime);
        }
    }

    private static void initInput() 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());

        lab = new int[N][N];
        activeViruses = new Virus[M];

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

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

                if (lab[i][j] == EMPTY) {
                    totalEmptyCells++;
                } else if (lab[i][j] == VIRUS) {
                    virusCandidates.add(new Virus(i, j, 0));
                }
            }
        }
    }

    // M개의 바이러스 조합 선택 (백트래킹)
    private static void chooseViruses(int start, int count) {
        if (count == M) {
            simulateSpread(totalEmptyCells);
            return;
        }

        for (int i = start; i < virusCandidates.size(); i++) {
            activeViruses[count] = virusCandidates.get(i);
            chooseViruses(i + 1, count + 1);
        }
    }

    // BFS 시뮬레이션
    private static void simulateSpread(int remainingEmpty) {
        boolean[][] visited = new boolean[N][N];
        Queue<Virus> queue = new LinkedList<>();

        for (Virus virus : activeViruses) {
            queue.add(new Virus(virus.x, virus.y, 0));
            visited[virus.x][virus.y] = true;
        }

        while (!queue.isEmpty()) {
            Virus current = queue.poll();

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

                if (isInBounds(nx, ny) && !visited[nx][ny] && lab[nx][ny] != WALL) {
                    visited[nx][ny] = true;

                    if (lab[nx][ny] == EMPTY) {
                        remainingEmpty--;
                    }

                    if (remainingEmpty == 0) {
                        minTime = Math.min(minTime, current.time + 1);
                        return;
                    }

                    queue.add(new Virus(nx, ny, current.time + 1));
                }
            }
        }
    }

    private static boolean isInBounds(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
}

---

문제 풀이 전략

 

M = 10이고, 바이러스의 개수도 10까지이기 때문에 조합을 통해 활성 바이러스의 위치를 먼저 정하고, BFS를 진행해도 된다고 생각했다.

 

또한, 이 문제에서 중요한 부분은 모든 바이러스가 활성 상태가 되어야 하는 것이 아니다! -> 정확하게는 모든 바이러스가 퍼지기면 되기만 하는 것이다.

문제를 정확히 이해하고 풀이하자.