백준 7569번: 토마토

 

좌표 그래프가 주어지고, 최소 일수를 찾아라?
BFS문제이다.

그런데 평소와 다른 점이 있다면 2차원 그래프가 아니라, 3차원 이라는 것이다.
x,y,z좌표가 헷갈리지 않도록 유의하면서 풀면 2차원과 크게 다르지 않다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int m, n, h;
    static int[][][] tomatos;
    static Queue<int[]> queue = new LinkedList<>();
    static int[] dz = {1, -1, 0, 0, 0, 0}; // 위, 아래
    static int[] dy = {0, 0, 1, -1, 0, 0}; // 앞, 뒤
    static int[] dx = {0, 0, 0, 0, 1, -1}; // 오른쪽, 왼쪽

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());

        tomatos = new int[h][n][m];

        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++) {
                    tomatos[z][y][x] = Integer.parseInt(st.nextToken());
                    if (tomatos[z][y][x] == 1) {
                        queue.add(new int[]{z, y, x});
                    }
                }
            }
        }

        int days = bfs();
        bw.write(String.valueOf(days));
        bw.flush();
        bw.close();
        br.close();
    }

    public static int bfs() {
        int days = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            boolean ripened = false;
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int z = current[0];
                int y = current[1];
                int x = current[2];

                // 위, 아래, 앞, 뒤, 오른쪽, 왼쪽 순으로 순회
                for (int dir = 0; dir < 6; dir++) {
                    int nz = z + dz[dir];
                    int ny = y + dy[dir];
                    int nx = x + dx[dir];

                    // 다음 영역이 유효하고 값이 0이면 탐색
                    if (nz >= 0 && nz < h && ny >= 0 && ny < n && nx >= 0 && nx < m && tomatos[nz][ny][nx] == 0) {
                        tomatos[nz][ny][nx] = 1;
                        queue.add(new int[]{nz, ny, nx});
                        ripened = true; // 토마토가 익음
                    }
                }
            }
            if (ripened) days++; // 토마토가 익었으면 하루가 증가
        }

        // bfs순회 끝난 후 안익은 토마토가 있으면 -1을 반환
        for (int z = 0; z < h; z++) {
            for (int y = 0; y < n; y++) {
                for (int x = 0; x < m; x++) {
                    if (tomatos[z][y][x] == 0) {
                        return -1;
                    }
                }
            }
        }

        return days;
    }
}