[Java] 7569 토마토 - BFS

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

7569번: 토마토

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static int M;
    static int N;
    static int H;
    static int[][][] map;
    static int del[][]  = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
    static int count;
    static Queue<zxy> queue;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        queue = new LinkedList<>();
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str);
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new int[H][N][M];
        for(int k=0;k<H;k++){
            for(int i=0;i<N;i++){
                str = br.readLine();
                st = new StringTokenizer(str);
                for(int j=0;j<M;j++){
                    map[k][i][j]= Integer.parseInt(st.nextToken());
                    if(map[k][i][j]==1) {
                        queue.offer(new zxy(k,i,j));
                    }
                }
            }
        }
        if(queue.size() ==H*N*M){
            System.out.println("0");
            return;
        }
        BFS();
        count =0;
        outer : for(int[][] ma : map){
            for(int m[] : ma){
                for(int a : m){
                    if(a==0){
                        System.out.println("-1");
                        return;
                    }else{
                        count = Math.max(count, a);
                    }
                }
            }
        }
        System.out.println(count-1);
 
    }
 
    public static void BFS(){
 
        while(!queue.isEmpty()) {
            int c_z = queue.peek().z; //queue에서 z,x,y 저장.
            int c_x = queue.peek().x;
            int c_y = queue.peek().y;
            queue.poll(); //queue에서 제
 
            for (int i = 0; i < 6; i++) {
                int n_z = c_z + del[i][0];
                int n_x = c_x + del[i][1];
                int n_y = c_y + del[i][2];
                if (isIn(n_z, n_x, n_y)) {
                    queue.offer(new zxy(n_z, n_x, n_y));
                    map[n_z][n_x][n_y] = map[c_z][c_x][c_y] +1 ;
                }
            }
        }
    }
    static boolean isIn(int h,int r, int c){
        return 0<=h && 0<=r && 0<=c && h<H && r<N && c<M && map[h][r][c] ==0;
    }
 
    public static class zxy {
        int z, x, y;
        zxy(int z, int x, int y){
            this.z = z;
            this.x = x;
            this.y = y;
        }
    }
}

 

토마토! BFS를 열심히 돌리는 문제다.

다만 다른점이 있다면 2차원으로만 풀던 다른 BFS랑 달리 3차원으로 푼다는 점..??

별다를건 없고 xy객체를 xyz객체로 바꾸고 delta 배열을 3자리로 바꾸기만 하면 얼추 비슷하게 된다.

 

이전과 같이 범위를 구하는 부분은 함수로 바꾸어 써주었고,

3차원이  이렇게 생겼다고 생각했기 때문에 del = {z좌표, x좌표(row), y좌표(col)}이렇게 된다고 생각했다

일단 시작하면서 1, 즉 처음 익은 애들을 모조리 큐에 넣어줬는데 큐의 크기가 3차원 박스의 부피만큼 같을 경우는

이미 다 익어버린 경우라 0을 출력했다.

 

맨 처음에 다 익었나 확인하기 위해서 한번에 1인애들을 돌면서 모두 큐에 넣었으니 BFS의 파라미터를 따로 안정해주었다.

BFS를 돌면서 상하좌우앞뒤를 확인한 후 범위 안에 있고 안익은 '0'이면  원래 익은정도에 +1을 해줬다.

 

상하좌우를 통해 갈 수 있는 0들을 다 확인했으면 마지막으로 혹시모를 0 개수를 세야겠지?

0이 하나라도 있으면 덜익은 토마토가 있는 것이므로 -1을 출력한다.

덜익은 토마토를 찾으며 가장 0을 1로 만드는데 오랜 시간이 걸린 토마토도 계속 찾아간다. 

 

다 익는데 얼마나 걸렸는지를 찾는것이므로 -1을 해주어야한다.

끄읕~