[Java] 백준 7569번 : 토마토

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

7569번: 토마토

[문제]

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

[입력]

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

 

[출력]

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

[예제 입력]

 

[풀이 과정]

3차원 배열을 가지고 풀어보았다.  익은 토마토의 인접한(상,하,좌,우,위,아래) 익지않은 토마토를 찾아야해서 bfs를 이용하였다. 3차원배열은 int [][][] 배열명 = new int[높이][행][열]; 이렇게 선언하니 헷갈리지 말자. 

 

1)먼저 입력값을 저장해놓은 3차원 배열에서 익은 토마토의 좌표값을 queue에 넣는다. (Dot라는 객체를 만들어 넣어주었다. )  

 

2) 1)에서 큐에 넣어둔 좌표값을 꺼낸다.  그  좌표값을 기준으로 상,하,좌,우,위,아래 좌표를 탐색하여 익지않은 토마토일 경우 큐에 익지않은 토마토의 좌표값을 넣는다. 그리고 안익은토마토[z][x][y] =익은토마토의 값[z][x][y] +1을 하여 날짜 수를 세어준다. 

 

3) 2)의 과정이 모두 끝나면 3차원 배열에서 가장 큰 값을 찾는다.

->찾는 도중에 0이 있다면 익지않은 토마토가 있기때문에 -1을 출력해준다.

->값이 1이라면 모두 익은상태였기때문에 0을 출력한다. 

->위의 경우가 모두 해당이 안된다면 가장큰값 -1 을 출력해주면된다. (맨 처음에 익은토마토의 값이 1이였기때문에 -1을 해서 날짜를 맞추어주면된다.)

 

[코드]

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


//토마토, 너비우선 탐색 ,3차원배열
public class Main {
    //상 하 좌 우 위 아래
    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 int M;
    static int N;
    static int H;
    static int [][][] box ;
    static Queue<Dot> queue;

    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];
        queue = new LinkedList<>();


        //3차원 배열에 입력값을 저장한다. //int [][][] 배열명 = new int[높이][행][열];
        for (int z=0 ; z<H;z++){ //높이
            for(int i = 0 ; i <N ; i++){ //세로
                st = new StringTokenizer(br.readLine()," ");
                    for (int j= 0; j<M; j++){ //가로
                        box[z][i][j] = Integer.parseInt(st.nextToken());

                        if(box[z][i][j]==1){ //익은 토마토의 좌표들을 큐에 넣는다.
                            queue.add(new Dot(i,j,z));
                        }
                }
            }
        }

        System.out.print(bfs());

    }

    public static  int bfs (){

        while (!queue.isEmpty()){
            Dot d = queue.poll(); //큐에 들어간 좌표값을 꺼낸다.

            int x =d.x;
            int y =d.y;
            int z =d.z;

            for (int i = 0 ; i < 6; i++){ // 상 하 좌 우 위 아래 순으로 다음 좌표를 가져온다.

                int nx = x+dx[i];
                int ny = y+dy[i];
                int nz = z+dz[i];

                if(nx >= 0  && ny >=0 && nz >=0 && nx<N && ny < M && nz < H){ //좌표범위가 3차원 배열 밖의 범위로 가면 안된다.

                       if (box [nz][nx][ny]==0){ //토마토가 익지 않았다면
                           queue.add(new Dot(nx,ny,nz)); //익지 않은 토마토 좌표의 값을 큐에 넣어준다.
                           box[nz][nx][ny]= box[z][x][y]+1; //그 전의 토마토 값의 +1을 더하여 날짜를 계산할 것이다.
                       }

                }
            }


        }


         int date = Integer.MIN_VALUE ; //최대 날짜 찾기

        for (int z=0 ; z<H;z++){ //높이
            for(int i = 0 ; i <N ; i++){ //세로

                for (int j= 0; j<M; j++){ //가로

                    if(box[z][i][j]==0){ //익지 않은 토마토가 존재하면 -1을 출력한다.
                        return -1;
                    }

                    date = Math.max(date,box[z][i][j]); // 익은 토마토 값 중에서 큰값으로 날짜를 갱신한다.
                }
            }
        }

         if(date==1){ //date 가 1이라는것은 토마토가 전부 익었던 상태였으므로 0을 리턴한다.
             return 0;

         }else {//그렇지 않으면 date -1 을 리턴한다. (맨처음 익은 토마토 값이 0이 아니라 1이였기때문에 1을 빼주어야한다)
             return date -1;
         }

    }

    public static class Dot {
        int x ;
        int y ;
        int z ;

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

 

[결과]