[백준] 7569 : 토마토 - Java

• 백준 문제 URL

---

문제 요약

토마토를 보관하는 상자가 (H)층으로 쌓여 있고, 각 층은 (N \times M) 격자 형태이다
익은 토마토(1)는 하루가 지나면 앞/뒤/좌/우/위/아래(6방향) 의 익지 않은 토마토(0)를 익게 만든다
모든 토마토가 익을 때까지 필요한 최소 일수를 출력하고, 끝까지 익지 못하면 -1, 처음부터 다 익어있으면 0을 출력한다

---

핵심 아이디어

“동시에 퍼져나가며 최소 일수”를 구하는 형태이므로 정답은 BFS다
시작점(처음부터 익은 토마토)이 여러 개일 수 있으니, 익은 토마토 좌표를 전부 큐에 넣고 시작하는 멀티 소스 BFS로 해결한다
box[nz][ny][nx] = box[z][y][x] + 1로 날짜를 누적 저장하면, 전체 탐색 후 최댓값에서 1을 빼서 최소 일수를 구할 수 있다

---

알고리즘 핵심 로직

• 입력을 받을 때 값이 1인 좌표를 전부 Queue에 넣는다(멀티 시작점)
• 큐에서 꺼낸 좌표 기준으로 6방향을 탐색하고, 값이 0이면 현재값 + 1로 바꾸고 큐에 추가한다
• BFS가 끝나면 전체를 순회하면서 0이 남아있으면 -1을 출력한다
• 0이 없다면 저장된 값 중 최댓값 max를 찾고 max - 1을 출력한다

---

전체 코드(제출용)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int M, N, H;
    static int[][][] box;
    static int[] dx = {1, -1, 0, 0, 0, 0};
    static int[] dy = {0, 0, 1, -1, 0, 0};
    static int[] dz = {0, 0, 0, 0, 1, -1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken()); // 가로(x)
        N = Integer.parseInt(st.nextToken()); // 세로(y)
        H = Integer.parseInt(st.nextToken()); // 높이(z)

        box = new int[H][N][M];
        Queue<int[]> q = new ArrayDeque<>();

        for (int z = 0; z < H; z++) {
            for (int y = 0; y < N; y++) {
                st = new StringTokenizer(br.readLine());
                for (int x = 0; x < M; x++) {
                    box[z][y][x] = Integer.parseInt(st.nextToken());
                    if (box[z][y][x] == 1) q.add(new int[]{z, y, x});
                }
            }
        }

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int z = cur[0], y = cur[1], x = cur[2];

            for (int dir = 0; dir < 6; dir++) {
                int nz = z + dz[dir];
                int ny = y + dy[dir];
                int nx = x + dx[dir];

                if (nz < 0 || nz >= H || ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
                if (box[nz][ny][nx] != 0) continue;

                box[nz][ny][nx] = box[z][y][x] + 1;
                q.add(new int[]{nz, ny, nx});
            }
        }

        int max = 1;
        for (int z = 0; z < H; z++) {
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < M; x++) {
                    if (box[z][y][x] == 0) {
                        System.out.println(-1);
                        return;
                    }
                    max = Math.max(max, box[z][y][x]);
                }
            }
        }

        System.out.println(max - 1);
    }
}