백준 7576번: 토마토

문제 출처: https://www.acmicpc.net/problem/7576

참고

BFS(Breadth-First Search): http://qlyh8.tistory.com/30?category=731166

BFS 문제: http://qlyh8.tistory.com/31?category=731166

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    private static int M, N;
    private static int[][] box;
    private static int[] dirX = {0, 1, 0, -1};
    private static int[] dirY = {1, 0, -1, 0};
 
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] input = reader.readLine().split(" ");
        M = Integer.parseInt(input[0]);
        N = Integer.parseInt(input[1]);
        box = new int[N][M];
 
        for(int i=0 ; i<N ; i++){
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            for(int j=0 ; j<M ; j++){
                box[i][j] = Integer.parseInt(tokenizer.nextToken());
            }
        }
 
        Queue<Tomato> queue = new LinkedList<>(); 
        for(int i=0 ; i<N ; i++){
            for(int j=0 ; j<M ; j++) {
                if (box[i][j] == 1) {
                    queue.offer(new Tomato(i, j));  // 처음에 익은 토마토를 모두 큐에 넣음
                }
            }
        }
 
        bfs(queue); // 안익은 토마토를 익은 토마토로 
 
        int count = 0;
        for(int i=0 ; i<N ; i++){
            for(int j=0 ; j<M ; j++){
                if(box[i][j] == 0){  // 모든 토마토가 익지 못함
                    System.out.println("-1"); 
                    return;
                }
                if(count < box[i][j]){ // 모든 토마토가 익을 때의 날짜
                    count = box[i][j];
                }
            }
        }
 
        System.out.println(count-1);
    }
 
    private static void bfs(Queue<Tomato> queue){
        while(!queue.isEmpty()){
            Tomato front = queue.peek();
            queue.poll(); // 익은 토마토 위치
 
            for(int k=0 ; k<4 ; k++){
                int newN = front.getN() + dirY[k]; // 익은 토마토 주변 4방향 Y
                int newM = front.getM() + dirX[k]; // 익은 토마토 주변 4방향 X
 
                if((0 <= newN && newN < N) && (0 <= newM && newM < M)){ // 상자 범위 내
                    if(box[newN][newM] == 0){ // 안익은 토마토라면
                        box[newN][newM] += box[front.getN()][front.getM()] + 1;  // 익은 토마토로 만듬, 날짜 갱신
                        queue.offer(new Tomato(newN, newM)); // 익었으므로 큐에 넣음
                    }
                }
            }
        }
    }
 
    public static class Tomato{
        int n, m;
 
        Tomato(int n, int m) {
            this.n = n;
            this.m = m;
        }
 
        int getN(){return n;}
 
        int getM(){return m;}
    }
}