[백준] 7569번 토마토 JAVA (자바) 풀이

문제 7569번 (bfs, 3차원 토마토 문제)

 :  토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 구하는 프로그램

 :  토마토는 격자모양 상자의 칸에 하나씩 넣은 다음 상자들을 수직으로 쌓아 올려서 창고에 보관
    상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다

 :  익은 토마토과 인접하면 익지 않은 토마토들 영향을 받는다

    인접한 곳 = 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토

 

   

 [입력]

 :  첫 줄에는 상자 가로크기 M, 상자 세로 크기 N, 쌓아올려지는 상자의 수 H (단, 2 ≤ M,N ≤ 100, 1 ≤ H ≤ 100)

 

 :  둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보

 

 :  1 = 익은 토마토, 0 = 익지 않은 토마토, -1 = 토마토가 들어있지 않은 칸

 

 

 [출력]

 :  여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력

 :  저장될 때부터 모든 토마토가 익어있는 상태 0 출력
 
 :  저장될 때부터 토마토가 모두 익지는 못하는 상황이면 -1 출력

 [설명]

 BFS 

 

 

 현재 정점에 연결된 가까운 점들부터 탐색

 

 Queue를 사용해서 구현

 

 

 

 

 

 [BFS 코드]

import java.io.*;
import java.util.*;
public class Main{
    static int dx[]={0,0,0,0,1,-1};
    static int dy[]={1,-1,0,0,0,0};
    static int dz[]={0,0,1,-1,0,0};
    static int M,N,H,arr[][][];
    static int result =0;
    static Queue<int[]> q = new LinkedList<>();
    
    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());
        
        arr = new int[H][N][M];
        
        
        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[i][j][k] = Integer.parseInt(st.nextToken());
                    
                    if(arr[i][j][k]==1){
                        q.add(new int[]{i,j,k,0});
                    }
                }
            }
        }
        bfs();
        
        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){
                        System.out.println(-1);
                        return;
                    }
                }
            }
        }
        System.out.println(result);
    }
    
    static void bfs(){
        while(!q.isEmpty()){
            int p[] = q.poll();
            for(int i=0; i<6; i++){
                int nz = p[0]+dz[i];
                int nx = p[1]+dx[i];
                int ny = p[2]+dy[i];
                
                if(0<=nz&&nz<H && 0<=nx&&nx<N && 0<=ny&&ny<M){
                    if(arr[nz][nx][ny]==0){
                        q.add(new int[] {nz,nx,ny,p[3]+1});
                        arr[nz][nx][ny] = 1;
                        result = p[3]+1;
                    }
                }
            }            
        }
    }
}

 

 

 [해설]
     

 :  static int arr[][][];  3차원 배열
    static int M,N,H;  첫째줄 입력
    static int result = 0;  카운트한 결과 저장
    static int[] dx = {0,0,1,-1,0,0}; 상,하,좌,우,위,아래 6방향의 x좌표
    static int[] dy = {1,-1,0,0,0,0};  상,하,좌,우,위,아래 6방향 y좌표
    static int[] dz = {0,0,0,0,1,-1};  상,하,좌,우,위,아래 6방향 z좌표
    static Queue<int[]> q = new LinkedList<>();  큐 생성

 

 :  st= new StringTokenizer(br.readLine()); 첫째줄 읽어오기
    M=Integer.parseInt(st.nextToken());  가로
    N=Integer.parseInt(st.nextToken());  세로
    H=Integer.parseInt(st.nextToken());  높이

         

 :  arr = new int[H][N][M];  3차원 배열 만들기 구현하기 쉬운 순서대로 M,H,N 배열한 것
        
 :  for(int i = 0; i<H; i++){  크기가 같은 2차원 배열을 H번 쌓을거라 맨 바깥에 지정

          for(int j = 0; j<N; j++){  StringTokenizer 때문에 줄(= N번) 단위로 받아야 계산하기 좋다
                st= new StringTokenizer(br.readLine());  한줄씩 입력받기
                for(int k = 0; k<M; k++){  마지막 M만큼 반복
                    arr[i][j][k] = Integer.parseInt(st.nextToken());  3차원 배열에 순서대로 입력값 넣기
                    
                    if(arr[i][j][k]==1) q.add(new int[]{i,j,k,0});  익은토마토( = 1 )면 이동가능 (큐에 넣기)
                }
          }
    }
 

 :  bfs();  bfs 실행

 

 :  for(int i=0;i<H;i++){  bfs를 돌리고나면 안익은 토마토들은 모두 1로 변경된다
            for(int j=0; j<N; j++){
                for(int k=0; k<M; k++){
                  if(arr[i][j][k]==0){  그럼에도 불구하고 하나라도 0이 나온다면 애초에 모두 안익은거
                        System.out.println(-1);  -1 출력
                        return;
                  }
                }
            }
    }
    

 :  System.out.println(result);  result 출력
    

 :  public static int bfs(){  bfs 돌리기
        while(!q.isEmpty()){  큐가 빌 때까지
            int[] p = q.poll();  큐에 있는 값들 빼서 p에 저장
             
            for(int i=0;i<6;i++){  6방향 탐색

                int nz = p[0] + dz[i];  p에서 z값 + 이동가능한 방향 = nz
                int nx = p[1] + dx[i];  p에서 x값 + 이동가능한 방향 = nx
                int ny = p[2] + dy[i];  p에서 y값 + 이동가능한 방향 = ny
                
                if(nx>=0 && nz>=0 && ny>=0 && nx<M && ny<N && nz<H){ 범위 지정
                     if(arr[nz][ny][nx]==0){  배열 안의 값이 0이면 익지 않은 토마토 
                          q.add(new int[]{nz,ny,nx,p[3]+1});  익지않은 토마토 큐에 넣고 익었다 카운
                          result = p[3]+1;  날짜 count
                     }
                }
           }
        }  
    }

 

 

이제 풀어보러 갈께요 :)

 

 

 

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

 

 

7569번: 토마토

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *