백준 7569 Java: 3차원 토마토를 Multi-Source BFS로 풀기

백준 7569는 M × N × H 상자에서 처음부터 익은 모든 토마토를 동시에 출발점으로 삼는 3차원 BFS 문제다. 여섯 방향 탐색 자체보다 여러 시작점을 같은 0일 차 queue에 넣고, 익지 않은 토마토 수를 끝까지 추적하는 것이 핵심이다.

입력 값을 정확히 해석하기

• 1: 익은 토마토
• 0: 익지 않은 토마토
• -1: 토마토가 들어 있지 않은 칸

원래 메모에서는 -1을 썩은 토마토라고 적었지만 문제에서 의미하는 것은 empty cell이다. M은 가로, N은 세로, H는 층 수이며 입력은 가장 아래 층부터 N줄씩 주어진다.

왜 Multi-Source BFS인가

익은 토마토가 여러 개라면 각각에서 BFS를 따로 돌리는 것이 아니다. 모든 익은 칸을 처음 queue에 넣으면 같은 distance의 칸이 함께 퍼져 나간다.

day 0: 처음 익은 모든 칸
day 1: day 0과 인접한 익지 않은 칸
day 2: day 1에서 새로 익은 칸의 이웃

각 칸을 처음 방문한 시점이 가장 빨리 익을 수 있는 날이다. unit edge graph에서 BFS가 최단 distance를 보장하기 때문이다.

Java 풀이

최대 모든 칸이 queue에 들어갈 수 있으므로, 좌표마다 new int[]를 만들지 않고 전체 칸 수 크기의 primitive int[] queue에 좌표를 encoding했다.

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    private static int width;
    private static int height;
    private static int layers;

    public static void main(String[] args) throws Exception {
        FastScanner scanner = new FastScanner();
        width = scanner.nextInt();
        height = scanner.nextInt();
        layers = scanner.nextInt();

        int[][][] box = new int[layers][height][width];
        int totalCells = width * height * layers;
        int[] queue = new int[totalCells];
        int head = 0;
        int tail = 0;
        int unripe = 0;

        for (int layer = 0; layer < layers; layer++) {
            for (int row = 0; row < height; row++) {
                for (int column = 0; column < width; column++) {
                    int state = scanner.nextInt();
                    box[layer][row][column] = state;

                    if (state == 1) {
                        queue[tail++] = encode(layer, row, column);
                    } else if (state == 0) {
                        unripe++;
                    }
                }
            }
        }

        int[] dl = {1, -1, 0, 0, 0, 0};
        int[] dr = {0, 0, 1, -1, 0, 0};
        int[] dc = {0, 0, 0, 0, 1, -1};
        int maxDayValue = 1;

        while (head < tail) {
            int position = queue[head++];
            int column = position % width;
            position /= width;
            int row = position % height;
            int layer = position / height;

            for (int direction = 0; direction < 6; direction++) {
                int nextLayer = layer + dl[direction];
                int nextRow = row + dr[direction];
                int nextColumn = column + dc[direction];

                if (nextLayer < 0 || nextLayer >= layers
                    || nextRow < 0 || nextRow >= height
                    || nextColumn < 0 || nextColumn >= width) {
                    continue;
                }
                if (box[nextLayer][nextRow][nextColumn] != 0) {
                    continue;
                }

                box[nextLayer][nextRow][nextColumn] =
                    box[layer][row][column] + 1;
                maxDayValue = Math.max(
                    maxDayValue,
                    box[nextLayer][nextRow][nextColumn]
                );
                unripe--;
                queue[tail++] = encode(nextLayer, nextRow, nextColumn);
            }
        }

        System.out.println(unripe == 0 ? maxDayValue - 1 : -1);
    }

    private static int encode(int layer, int row, int column) {
        return (layer * height + row) * width + column;
    }

    private static final class FastScanner {
        private final BufferedInputStream input =
            new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int index;
        private int size;

        int nextInt() throws IOException {
            int value = 0;
            int sign = 1;
            int current;

            do {
                current = read();
            } while (current <= ' ');

            if (current == '-') {
                sign = -1;
                current = read();
            }
            while (current > ' ') {
                value = value * 10 + current - '0';
                current = read();
            }
            return value * sign;
        }

        private int read() throws IOException {
            if (index >= size) {
                size = input.read(buffer);
                index = 0;
                if (size < 0) {
                    return -1;
                }
            }
            return buffer[index++];
        }
    }
}

box에는 원래 상태와 day를 함께 저장한다. 처음 익은 칸이 1이고 그 이웃이 2이므로 최종 answer는 최대 값에서 1을 뺀다.

원래 풀이에서 바로잡은 경계

처음부터 0인 칸이 하나도 없다면 모두 익는 데 걸리는 최소 일수는 0이다. 원래 설명의 “1을 출력”은 잘못 적은 값이었고 실제 code는 0을 출력하고 있었다.

또한 BFS가 끝났다고 모든 토마토가 익은 것은 아니다. -1 벽으로 완전히 둘러싸인 0은 queue에 들어오지 못한다. 처음 센 unripe를 새로 익힐 때마다 줄이고, 종료 후 0인지 확인하면 별도 3차원 scan 없이 판정할 수 있다.

복잡도

각 칸은 최대 한 번 queue에 들어가고 여섯 neighbor를 확인한다.

• 시간 복잡도: O(MNH)
• 공간 복잡도: O(MNH)

2차원 BFS의 기본 흐름은 미로 탐색 Java 풀이, graph traversal의 공통 원리는 그래프와 DFS·BFS에서 이어서 볼 수 있다.

참고 자료

• 백준 7569 토마토