[문제 풀이] 백준 7576번 토마토 JAVA

문제

  문제접근 방법   

해당 문제는 상자에 담긴 토마토가 익어가는 과정을 조사하는 문제로 익은 토마토는 하루가 지날 때마다 인접한 토마토를 익게 만든다. 상자의 크기와 각 칸의 토마토 상태(익음, 안 익음, 없음)가 입력으로 주어질 때

모든 토마토가 다 익을 때까지 걸리는 최소 일수를 구해야 한다. 만약 끝까지 익지 못하는 토마토가 존재한다면 -1을 출력한다.

해당 문제는 앞서 풀어보았더 7569번 토마토 문제의 하위호환 문제라고 생각된다. 앞서 풀었던 문제는 3차원 문제였고 본 문제는   2차원 문제라는 차이말고는 모든것이 같다. 또 이미 3차원으로 비슷하게 구현해보았기 떄문에 쉽게 구현이 가능했다.                  핵심은 토마토 익는 일수 관리를 어떤식으로 할지와 익은 토마토가 동시에 퍼지는 것을 어떤식으로 구현할지이다.

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static Queue<int[]> q=new LinkedList<>();
    public static int ripeCnt=Integer.MAX_VALUE;
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int m=s.nextInt();
        int n=s.nextInt();
        int storage[][]=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                storage[i][j]=s.nextInt();
                if(storage[i][j]==1)q.offer(new int[]{i,j,0});
            }
        }
        int xy[]=q.poll();
        bfs(xy[0],xy[1],storage);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(storage[i][j]==0)ripeCnt=-1;
            }
        }
        System.out.print(ripeCnt);
    }
    public static void bfs(int x,int y,int storage[][]){
        
        q.offer(new int[]{x,y,0});
        
        int dx[]={-1,1,0,0};
        int dy[]={0,0,-1,1};
        int cnt=0;
        while(!q.isEmpty()){
            int xyCnt[]=q.poll();
            
            for(int i=0;i<4;i++){
                int nx=dx[i]+xyCnt[0];
                int ny=dy[i]+xyCnt[1];
                cnt=xyCnt[2];
                if(nx>=0&&ny>=0&&nx<storage.length&&ny<storage[0].length){
                    if(storage[nx][ny]!=-1&&storage[nx][ny]==0){
                        storage[nx][ny]=1;
                        q.offer(new int[]{nx,ny,cnt+1});
                    }
                }
            }
        }
        ripeCnt=ripeCnt>cnt?cnt:ripeCnt;
    }
}

먼저 익은 토마토가 인접한 토마토들을 동시에 익히게 하려면 Queue에 익어있는 토마토들의 좌표들을 모두 넣어주고 코드를 작성하면 동시에 익는 기능 구현이 가능하다. 또 익는 일수 또한 cnt로 관리하다가 reipeCnt와 비교해서 가장 작은 값을 저장하게

코드를 작성하였고 이후 토마토 저장소에 0이 있는지 없는지를 확인해 reipeCnt를 -1로 출력할지 그대로 출력할지를 결정할 수 있게 구현하였다.

 

  마무리  

앞서 토마토 문제를 풀어보아서 한 번에 전염되는 방식에 대해 알고 익숙해져 있어서 손쉽게 풀이가 가능했지만 일반적으로 처음 접하는 문제라면 어렵게 느껴지는 것이 당연하다고 생각되는 문제이다. 만약 7569번 토마토 문제를 풀어보지 않았다면 해당 문제를 풀이한 이후에 해결하는 것도 좋을듯하다. 헛갈리는 부분을 완벽하게 채워줄 것이라고 생각된다.

 참고 자료 

• 토마토

[문제 풀이] 백준 7569번 토마토 JAVA