7569번 문제

문제

풀어본 적이 있는 것만 같은 토마토 문제 ..
분명히 풀어본 적 있는 것 같은데 문제를 읽어보니 3차원 배열을 사용해야 하는 문제였다. 이전에 푼 건 2차원 배열이었던듯 ..?? 🧐

풀이

하루마다 익을 수 있는 토마토를 체크하고, 그 다음날로 넘어가야 한다.
따라서 dfs가 아닌 bfs를 사용해서 토마토를 익힌다 (!)

토마토가 모두 익을 때까지 최소 며칠이 걸리는지에 대한 계산은, 자료구조 int box[][][]를 통해 익은 토마토에 대해서 마킹할 때 해당 토마토가 익은 날이 언제인지를 기록했다.
이후 모든 토마토가 빠짐없이 익었다면, box에서 최댓값 max를 찾아 익는 데 가장 오래 걸린 토마토의 값을 찾았다.

import java.io.*;
import java.util.ArrayList;
import java.util.List;
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};
    static List<int[]> tomato = new ArrayList<>();
    static int cnt = 0;
    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());
        box = new int[H][N][M];
        for(int k=0; k<H; k++) {
            for(int i=0; i<N; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<M; j++) {
                    box[k][i][j] = Integer.parseInt(st.nextToken());
                    if(box[k][i][j] == 1) tomato.add(new int[] {k,i,j});
                    if(box[k][i][j] == 0) cnt++;
                }
            }
        }

        processRipening(0);
        int result = -1;
        if(cnt == 0) {
            int max = 0;
            for(int k=0; k<H; k++) {
                for(int i=0; i<N; i++) {
                    for(int j=0; j<M; j++) {
                        if(max < box[k][i][j]) max = box[k][i][j];
                    }
                }
            }
            result = max-1;
        } 
        System.out.println(result);
    }

    public static void processRipening(int idx) {
        for(int t=idx; t<tomato.size(); t++) {
            int[] pos = tomato.get(t);
            for(int i=0; i<6; i++) {
                int nz = pos[0]+dz[i];
                int nx = pos[1]+dx[i];
                int ny = pos[2]+dy[i];
                
                if(nz<0 || nz>=H || nx<0 || nx>=N || ny<0 || ny>=M) {
                    continue;
                }

                if(box[nz][nx][ny] == 0) {
                    box[nz][nx][ny] = box[pos[0]][pos[1]][pos[2]]+1;
                    tomato.add(new int[] {nz,nx,ny});
                    cnt--;
                }
            }
        }
    }
}

코드를 보면 result에 max-1를 넣는 것을 볼 수 있다.

이는 processRipening(0) 로 메서드를 호출하고,
해당 메서드에서 토마토를 익힘처리 할 때

box[nz][nx][ny] = box[pos[0]][pos[1]][pos[2]]+1;

위와 같이 처리되기 때문에, 첫째날 익은 토마토가 2로 마킹된다.

따라서 max-1을 해주는 것이다 !

---