[BOJ] 7576. 토마토

BFS를 사용하는 문제이다.

모든 시작점 1을 queue에 집어넣은 다음 평소 boolean배열 형태로 사용하던 visit를 int배열 형태로 바꾸어 토마토가 익은 날짜로 대신하여 사용하였다. 그리고 이미 visit배열이 갱신되었더라도 더 작은 날짜를 가질 수 있다면 갱신할수 있도록 while문 안쪽에서 구현하였다.

 

package chap05;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_7576_토마토 {
    
    static int N,M;
    static int[] di = {-1,0,1,0};
    static int[] dj = {0,1,0,-1};
    
    static int[][] map;
    static int[][] visit;
    
    static Queue<Pos> queue;
    
    static class Pos{
        int i,j;
        public Pos(int i,int j) {
            this.i=i; this.j=j;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        st=new StringTokenizer(br.readLine());
        M=Integer.parseInt(st.nextToken());
        N=Integer.parseInt(st.nextToken());
        
        visit = new int[N][M];
        map=new int[N][M];
        
        for(int i=0;i<N;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++) {
                visit[i][j]=-1;
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        
        queue= new LinkedList<>();
        bfs();
        
        System.out.println(findResult());
    }
    
    static void bfs() {
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                if(map[i][j]==1 && visit[i][j]<0) {
                    queue.offer(new Pos(i, j));
                    visit[i][j]=0;
                }
            }
        }
        
        while(!queue.isEmpty()) {
            Pos cur = queue.poll();
            int day = visit[cur.i][cur.j];
            
            for(int dir=0;dir<4;dir++) {
                int nextI = cur.i+di[dir];
                int nextJ = cur.j+dj[dir];
                
                if(nextI<0 || nextI>=N || nextJ<0 || nextJ>=M)
                    continue;
                
                if(map[nextI][nextJ]==0 ) {
                    if(visit[nextI][nextJ]==-1) {
                        visit[nextI][nextJ]=day + 1;
                        queue.offer(new Pos(nextI, nextJ));
                    }else if(visit[nextI][nextJ] > day+1) {
                        visit[nextI][nextJ]=day + 1;
                        queue.offer(new Pos(nextI, nextJ));
                    }
                }
            }
        }
    }
    
    static int findResult() {
        
        int max=-1;
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                if(visit[i][j]==-1 && map[i][j]==0)    //0인데 방문을 안한곳이 있으면 
                    return -1;
                if(visit[i][j]>max)
                    max=visit[i][j];
            }
        }
        return max;
    }
    
}