BFS - 백준7576 토마토

이 문제의 관건은 처음 시작할 때 익은 토마토가 여러개 일 수 있다는 것이므로, 츠마리 bfs탐색이 여러 곳에서 동시에 시작된다는 점이다.
해답은 의외로 간단했다. 시작 지점을 모두 처음에 큐에 넣고 시작하면 되는 것이었다.
+그리고 미로탐색 문제와 마찬가지로 토마토가 익은 날짜를 Pair의 세번째 변수에 저장하고, 꺼낼때 마다 현재 날짜와 그 토마토가 익은 날짜를 비교해 업데이트했다.

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        
        int[][] arr = new int[n][m];
        Queue<Pair> queue = new LinkedList<>();
        
        // 이미 모두 익어있는 경우
        boolean otherCase = true;
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++){
                int tmp = Integer.parseInt(st.nextToken());
                if(tmp == 0){
                    otherCase = false;
                }
                if(tmp == 1){
                    queue.add(new Pair(i,j,0));            //처음 익은 토마토들 위치 넣기
                }
                arr[i][j] = tmp;
            }
        }
        if(otherCase){
            System.out.println(0);
        }else{
            //동서남북배열

            //while(!큐.isEmpty)
            //하나꺼내기
            //for(동서남북)
            //중 위치하나 확정
            //if(boundary exception체크)
            //if(벽or방문한곳인지)
            //방문표시후 큐에 삽입
            
            int[] bx = {1, 0, -1, 0};
            int[] by = {0, 1, 0, -1};
            
            while(!queue.isEmpty()){
                Pair nowPos = queue.poll();
                int thisDate = nowPos.n + 1;

                for(int i = 0; i < 4; i++){
                    int px = nowPos.x + bx[i];
                    int py = nowPos.y + by[i];
                    if(px < 0 || px > n-1 || py < 0 || py > m-1){
                        continue;
                    }
                    if(arr[px][py] != 0){
                        continue;
                    }
                    arr[px][py] = thisDate;
                    queue.add(new Pair(px,py,thisDate));
                }
            }
            //다 돌면서 다 익었는지 + 최고 date검사
            boolean yetTomato = false;
            int finishDate = 0;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    if(arr[i][j] == 0){
                        yetTomato = true;
                        break;
                    }
                    if(arr[i][j] > finishDate){
                        finishDate = arr[i][j];
                    }
                }
                if(yetTomato){
                    break;
                }
            }
            
            if(yetTomato){
                System.out.println(-1);
            }else{
                System.out.println(finishDate);
            }
        }
    }
    
    static class Pair{
        int x;
        int y;
        int n;
        Pair(int x, int y, int n){
            this.x = x;
            this.y = y;
            this.n = n;
        }
    }
}

+ 당연히 첫번째 입력의 첫번째 숫자가 행, 두번째가 열인줄 알고 풀었는데, 나중에 보니 반대였다.
그래서 마지막에 입력받는 코드의 m과 n을 바꿔주었다.

역시 백준은 문제를 꼼꼼하게 읽어야 한다. ..