문제 출처

단계별로 풀어보기 > 그래프와 순회 > 토마토(7569)
https://www.acmicpc.net/problem/7569

문제 설명

상자의 크기를 나타내는 두 정수 M,N 쌓아올려지는 상자의 수 H가 주어진다.
그리고, 각 칸에는 토마토가 있거나 없는데, 토마토가 없는 경우는 -1, 익은 토마토가 있는 경우는 1, 안 익은 토마토가 있는 경우는 0으로 주어진다.
익은 토마토 옆에 안 익은 토마토가 있는 경우 하루 뒤, 안 익은 토마토는 익은 토마토가 된다.
이 경우에 토마토가 다 익는데 걸리는 시간을 구하라

접근 방법

이전 토마토 문제와 비슷하지만, z축이 생긴 버전이다. 하지만 문제 풀이 방법은 똑같다.
토마토 정보를 담는 3차원 배열 arr 와, 방문 여부 및 날짜를 기록하는 3차원 배열 visited를 생성한다.
이 후, bfs를 진행한다.
bfs 시작할 때, 0일차에 익은 토마토가 있는 위치를 전부 삽입 후 진행한다.
이후 상, 하, 좌, 우, z축 기준 위, z축 기준 아래까지 경우의 수를 모두 판단하여 bfs 탐색을 진행한다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 토마토_2 {
    public static int arr[][][];
    public static int visited[][][];

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

    public static void bfs(){
        Queue<int[]> q = new LinkedList<>();

        for(int i = 0; i < arr[0].length; i++){
            for(int j = 0; j < arr.length; j++){
                for(int k = 0; k < arr[0][0].length; k++){
                    if(arr[j][i][k] == 1){
                        q.add(new int[]{j,i,k});
                        visited[j][i][k] = 0;
                    }
                }
            }
        }

        while(!q.isEmpty()){
            int[] cur = q.poll();

            for(int i = 0; i < 6; i++){
                int nx = cur[1] + dx[i];
                int ny = cur[0] + dy[i];
                int nz = cur[2] + dz[i];

                if(nx < 0 || nx >= arr[0].length || ny < 0 || ny >= arr.length || nz < 0 || nz >= arr[0][0].length) continue;
                if(arr[ny][nx][nz] == -1) continue;
                if(visited[ny][nx][nz] != -1) continue;

                visited[ny][nx][nz] = visited[cur[0]][cur[1]][cur[2]] + 1;
                arr[ny][nx][nz] = 1;

                q.add(new int[]{ny,nx,nz});
            }
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());


        arr = new int[N][M][H];
        visited = new int[N][M][H];

        for(int i = 0; i < H; i++){
            for(int j = 0; j < N; j++){
                st = new StringTokenizer(br.readLine());
                for(int k = 0; k < M; k++){
                    arr[j][k][i] = Integer.parseInt(st.nextToken());
                    visited[j][k][i] = -1;
                }
            }
        }

        bfs();

        int result = 0;

        for(int i = 0; i < H; i++){
            for(int j = 0; j < N; j++){
                for(int k = 0; k < M; k++){
                    if(arr[j][k][i] == 0 && visited[j][k][i] == -1){
                        bw.write(String.valueOf(-1));
                        bw.flush();
                        bw.close();
                        br.close();
                        return;
                    }
                    result = Math.max(result, visited[j][k][i]);
                }
            }
        }
        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();

    }
}

알게된 점

시간 복잡도는 O(M x N x H)이다.

문제푼 흔적