[BOJ] 7569: 토마토 (JAVA)

문제

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

 

여담

토마토 문제와 거의 유사하다. 다른 점은 2차원에서 3차원으로 변경됐다는 것 정도? 그래서 문제 제목도 같나 보다. 토마토 문제를 풀고 바로 푸는 것이라 쉽게 풀 수 있었다.

 

풀이

토마토들이 다 익는 최소 일수를 알고 싶은 것이므로 BFS 탐색을 수행하면 된다. 언급했듯이 이전에 풀었던 토마토 문제와 거의 유사하므로, 풀이 방법은 토마토 풀이 게시글을 참고하면 된다. 

 

주의해야 할 점은 2차원이 아니라 3차원이라는 점이다. 따라서 상하좌우뿐만 아니라 위, 아래로도 BFS 탐색을 수행해야 한다.

 

코드

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

public class Main {
    static int M, N, H;
    static int[][][] box;
    static boolean[][][] visited;
    static Queue<Pos> queue = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        // 이젠 z 방향으로도 퍼진다!
        box = new int[N][M][H];
        visited = new boolean[N][M][H];

        int tomato = 0;
        for (int h = 0; h < H; h++) {
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < M; j++) {
                    box[i][j][h] = Integer.parseInt(st.nextToken());
                    if (box[i][j][h] != -1) tomato++;
                    if (box[i][j][h] == 1) {
                        queue.offer(new Pos(i, j, h));
                        visited[i][j][h] = true;
                    }
                }
            }
        }
        // 저장될 때부터 모든 토마토가 익어있는 상태
        if (tomato == queue.size()) {
            System.out.println(0);
            return;
        }

        System.out.println(bfs());
    }

    static int bfs() {
        int[][] move = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}};
        while (!queue.isEmpty()) {
            Pos pos = queue.poll();

            for (int i = 0; i < 6; i++) {
                int nx = pos.x + move[i][0];
                int ny = pos.y + move[i][1];
                int nz = pos.z + move[i][2];
                if (nx < 0 || ny < 0 || nz < 0 || nx >= N || ny >= M || nz >= H ||
                        visited[nx][ny][nz] || box[nx][ny][nz] == -1) {
                    continue;
                }

                box[nx][ny][nz] = box[pos.x][pos.y][pos.z] + 1;
                visited[nx][ny][nz] = true;
                queue.offer(new Pos(nx, ny, nz));
            }
        }

        int max = 0;
        for (int h = 0; h < H; h++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (box[i][j][h] == 0) return -1;
                    max = Math.max(max, box[i][j][h]);
                }
            }
        }
        return max - 1;
    }

    static class Pos {
        int x, y, z;

        Pos(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }
}

---