백준 7569 '토마토' (3차원)

DoubleDeltas·2024년 10월 10일

알고리즘 문제풀이

목록 보기

107/110

아이디어

3차원 배열에 토마토 정보를 저장하고, 익은 토마토 칸들을 시작으로 한 칸씩 BFS로 탐색한다.
BFS의 너비가 1 늘어날 때마다 정답에 1을 추가한다.
탐색 결과 발견된 토마토 개수가 저장된 토마토 총 개수와 같으면 누적한 정답이 그대로 정답이고, 아닌 경우는 토마토가 모두 익을 수 있는 방법이 없는 경우이므로 -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 BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tk = null;

    static final int RIPEN = 1, UNRIPEN = 0, EMPTY = -1;

    static int ans;

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

    static int M, N, H;
    static int[][][] map;
    static int cnt, tomato;

    static Queue<Data> q = new ArrayDeque<>();
    static boolean[][][] enqueued;

    public static void main(String[] args) throws Exception {
        tk = new StringTokenizer(rd.readLine());
        M = Integer.parseInt(tk.nextToken());   // x: 열
        N = Integer.parseInt(tk.nextToken());   // y: 행
        H = Integer.parseInt(tk.nextToken());   // z: 높이

        map = new int[H][N][M];
        enqueued = new boolean[H][N][M];

        for (int z=0; z<H; z++) {
            for (int y=0; y<N; y++) {
                tk = new StringTokenizer(rd.readLine());
                for (int x=0; x<M; x++) {
                    map[z][y][x] = Integer.parseInt(tk.nextToken());
                    if (map[z][y][x] == RIPEN) {
                        q.offer(new Data(z, y, x));
                        enqueued[z][y][x] = true;
                        cnt++;
                    }
                    if (map[z][y][x] != EMPTY)
                        tomato++;
                }
            }
        }

        while (true) {
            int size = q.size();
            for (int i=0; i<size; i++) {
                Data data = q.poll();
                int z = data.z;
                int y = data.y;
                int x = data.x;
                for (int d=0; d<6; d++) {
                    int nz = z + dz[d];
                    int ny = y + dy[d];
                    int nx = x + dx[d];
                    if (nz < 0 || nz >= H || ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
                    if (map[nz][ny][nx] == EMPTY) continue;
                    if (enqueued[nz][ny][nx]) continue;

                    q.offer(new Data(nz, ny, nx));
                    enqueued[nz][ny][nx] = true;
                    map[nz][ny][nx] = RIPEN;
                    cnt++;
                }
            }
            if (q.isEmpty()) break;
            ans++;
        }

        if (cnt < tomato)
            System.out.println(-1);
        else
            System.out.println(ans);
    }

    static class Data {
        int z, y, x;
        Data(int z, int y, int x) {
            this.z = z;
            this.y = y;
            this.x = x;
        }
    }
}