[JAVA] 토마토 (백준 7569)

이 문제는 2차원이 아니라 3차원으로 bfs푸는 것이다. 

 

또한 익기 시작하는 지점이 정해진 것도 아니며 여러개가 있을 수도 있고 없을 수도 있다. 

 

관건은 모든 토마토가 익었는지 확인하는 것과 모두 익었다면 며칠이 걸리는지 구하는 것이 핵심이다.

 

본인이 접근한 방법대로 2층짜리  3x3 토마토상자가 있다고 가정하고 풀어보는 예시를 보자.

 

예)

(z,x,y) 에서 z 는 높이이며 , x 는 가로, y는 세로다. x,y,z 모두 0부터 시작한다.

시작전 ( 0초 )

큐에 남은 좌표 : (0,1,1) 

 

1층

0	0	0
0	1	0
0	0	0

 

2층

 

0	0	0
0	0	0
0	0	0

 

1초후

큐에 남은 좌표: (0,0,1) , (0,1,0), (0,2,1) , (0,1,2)

 

1층

0	2	0
2	1	2
0	2	0

 

2층

 

0	0	0
0	2	0
0	0	0

 

 

2초후

큐에 남은 좌표들 : (0,0,0) , (0,0,2) , (0,2,0) , (0,2,2) , (1,0,1) ,  (1,1,0) ,  (1,2,1),  (1,1,2)

 

1층

3	2	3
2	1	2
3	2	3

 

2층

 

0	3	0
3	2	3
0	3	0

 

3초후

큐에 남은 좌표들 : (1,0,0), (1,0,2), (1,2,0), (1,2,2)

 

1층

3	2	3
2	1	2
3	2	3

 

2층

 

4	3	4
3	2	3
4	3	4

 

1층과2층중 가장 큰 값에서 1을 빼면 된다.

 

따라서 답은 3초이다.

 

모두 익었는지 확인하는 방법은 1층과 2층중에 0이 없으면 모두 익은 것이다. 

 

전체 로직은 아래에 코드 참고.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
    static int m,n,h;
    static int[][] d6 = {
            {1,0,0},
            {-1,0,0},
            {0,1,0},
            {0,-1,0},
            {0,0,1},
            {0,0,-1}
    }; // 위,아래,상,하,좌,우

    public static void main(String[] args) throws IOException{
        FastScanner fs = new FastScanner();
        m = fs.nextInt();
        n = fs.nextInt();
        h = fs.nextInt();
        int arr[][][] = new int[h][n][m];
        int visited[][][] = new int[h][n][m];
        for(int i=0;i<h;i++) arr[i] = fs.read2DArray(m,n);

        Queue<Pos> q = new LinkedList<>();
        for(int i=0;i<h;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<m;k++){
                    if(arr[i][j][k]==1){
                        q.offer(new Pos(i,j,k));
                        visited[i][j][k]=1;
                    }
                }
            }
        }

        while(!q.isEmpty()){
            Pos cur = q.poll();

            for(int i=0;i<6;i++){
                int nh = cur.z + d6[i][0];
                int nx = cur.x + d6[i][1];
                int ny = cur.y + d6[i][2];

                if(nh>=0 && nh<h
                && nx>=0 && nx<n
                && ny>=0 && ny<m
                && visited[nh][nx][ny]==0
                && arr[nh][nx][ny] == 0){
                    visited[nh][nx][ny]=1;
                    arr[nh][nx][ny] = arr[cur.z][cur.x][cur.y] + 1;
                    q.offer(new Pos(nh,nx,ny));
                }
            }
        }

//        print3DArray(arr);
        System.out.println(ans(arr,visited));



    }


    public static void print3DArray(int[][][] a){
        Arrays.stream(a).forEach(
                o->{
                    Arrays.stream(o).forEach(
                            k->{
                                Arrays.stream(k).forEach(System.out::print);
                                System.out.println();
                            }
                    );
                    System.out.println();
                }
        );
    }

    static int ans(int[][][] arr,int[][][] visited){
        int answer = 0;
        for(int i=0;i<h;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<m;k++){
                    if(arr[i][j][k]==0 && visited[i][j][k]==0)
                        return -1;
                    answer = answer > arr[i][j][k]-1?answer:arr[i][j][k]-1;
                }
            }
        }
        return answer;
    }


    static class Pos{
        int z,x,y;

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

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public String next() throws IOException {
            while(!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException{
            return Integer.parseInt(next());
        }

        public int[] readArray(int m) throws IOException{
            int[] a = new int[m];
            for(int i=0;i<m;i++) a[i] = nextInt();
            return a;
        }

        public int[][] read2DArray(int m,int n) throws IOException{
            int[][] a = new int[n][m];
            for(int i=0;i<n;i++) a[i] = readArray(m);
            return a;
        }

    }
}