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

문제 7576번 (2차원 토마토 문제)

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

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

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

    인접한 곳 = 상, 하, 좌, 우 4가지 방향에 있는 토마토

 

   

 [입력]

 :  첫 줄에는 상자 가로크기 M, 상자 세로 크기 N

 

 :  둘째 줄부터는 저장된 토마토들의 가로 세로 정보

 

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

 

 

 [출력]

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

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

 [설명]

 

 BFS 

 

 

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

 

 Queue를 사용해서 구현

 

 

 

 

 

 [BFS 코드]

import java.io.*;
import java.util.*;
import java.awt.*;
public class Main{
    static int arr[][];
    static int M,N;
    static int value = 0;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static Queue<Point> q = new LinkedList<>();
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st= new StringTokenizer(br.readLine());
        
        M=Integer.parseInt(st.nextToken());
        N=Integer.parseInt(st.nextToken());
      
        arr = new int[N][M];
 
        for(int i = 0; i<N; i++){
            st= new StringTokenizer(br.readLine());
            for(int j = 0; j<M; j++){
                    arr[i][j]=Integer.parseInt(st.nextToken());
                    
                    if(arr[i][j]==1) {
                        q.add(new Point(i,j)); 
                    }
            }
        }
        System.out.println(bfs());
    }
    
    public static int bfs(){
        while(!q.isEmpty()){
            Point p = q.poll();
             
            for(int i=0;i<4;i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                
                if(nx>=0 && ny>=0 && nx<N && ny<M){
                    if(arr[nx][ny]==0){
                        q.add(new Point(nx,ny));
                        arr[nx][ny] = arr[p.x][p.y] + 1;
                    }
                }
            }
        }
            
        for (int i = 0; i <N; i++) {
            for (int j = 0; j <M; j++) {
                    if(arr[i][j] == 0) {
                        return -1;
                    }
                    value = Math.max(value, arr[i][j]); 
            }
        }
       if(value == 1)
    		return 0;
    	else
    		return value - 1;
        }    
}

 

 

 [해설]
     

 :  static int arr[][];  2차원 배열
    static int M,N;  첫째줄 입력
    static int value = 0;  결과값 초기화
    static int[] dx = {0,0,1,-1}; 상,하,좌,우 4방향의 x좌표
    static int[] dy = {1,-1,0,0};  상,하,좌,우 4방향의 y좌표
    static Queue<Point> q = new LinkedList<>();  큐 생성

 

 

 :  st= new StringTokenizer(br.readLine()); 첫째줄 읽어오기
    M=Integer.parseInt(st.nextToken());  가로 개수 = 열 개수
    N=Integer.parseInt(st.nextToken());  세로 개수 = 행 개수

         

 :  arr = new int[N][M];  2차원 배열 모양 만들기 arr[행][열]
         
 :  for(int i = 0; i<N; i++){  줄(= N번) 단위로 받아야 계산하기 좋다

          st= new StringTokenizer(br.readLine()); 

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

                  arr[i][j] = Integer.parseInt(st.nextToken());  2차원 배열에 순서대로 입력값 넣기
                  if(arr[i][j]==1) q.add(new Point(i,j));  익은토마토( = 1 )면 해당 좌표 큐에 넣기
                   
                }
          }
    }

 

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

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

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

                       if(arr[i][j] == 0) {  만약 모든 값이 0이였다면 모두 안익은 상태니까 -1 출력
                           return -1;  
                       }
                       value = Math.max(value, arr[i][j]);  value = 배열 안의 데이터 중 가장 큰 값 저장
              }
        }

        if(value==1) { 최댓값 1이면 다 익은 상태 0 출력해

            return 0;  

        }

        else return value -1;  그밖의 경우여도 value -1 해서 출력하면 답나온다
        }    

 

 

이제 풀어보러 갈께요 :)

 

 

 

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

7576번: 토마토

 

 

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