<Algorithm> 34. 7576번 토마토

1. 7576번 토마토

• 기본 BFS 문제, 영역이 하루에 한번씩만 늘어나기 때문에 BFS를 활용하여 level을 출력한다. 

• 주의할 점은 DFS는 영역의 깊이를 탐색하기 때문에 BFS로 푸는 것이 더 쉽게 풀수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    
    static boolean[][] visited;
    static int[][] dist;
    static int max = 0;
    public static void main(String[] args) throws NumberFormatException, 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];
        visited = new boolean[N][M];
        dist = 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());
            }
        }
        
        Queue<Coordinate> queue = new LinkedList<>();
        
        for(int i = 0; i < N; i ++) {
            for(int j = 0; j < M; j++) {
                if(arr[i][j] == 1) { // 처음 시작할때 익은 토마토 탐색
                    queue.add(new Coordinate(i, j));
                    visited[i][j] = true;
                    dist[i][j] = 0; 
                }
            }
        }
        
        bfs(arr, queue, M, N);
        
        for(int i = 0; i < N; i ++) {
            for(int j = 0; j < M; j++) {
                if(arr[i][j] == 0) {
                    System.out.println(-1); // 다 익지 못한 경우
                    return;
                }
            }
        }
        
        System.out.println(max);
        
    }
    
    public static void bfs(int[][] arr, Queue<Coordinate> queue, int M, int N) { 
        
        int[] dx = {0, 0, 1, -1}; 
        int[] dy = {1, -1, 0, 0};
        
        
        while(!queue.isEmpty()) {
            Coordinate loc = queue.remove();
            int x = loc.x;
            int y = loc.y;
            
            for(int i = 0; i < dx.length ; i ++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny] && arr[nx][ny] == 0) {
                    // 상하좌우 방문 안했을 경우 && 안익은 토마토 일경우
                    queue.add(new Coordinate(nx, ny));
                    visited[nx][ny] = true;
                    dist[nx][ny] = dist[x][y] + 1; // 걸린 일수
                    arr[nx][ny] = 1; // 익은 토마토 표시
                    
                    if(max < dist[nx][ny]) {
                        max = dist[nx][ny]; // 가장 오래걸린 일수가 모두 익은 일수
                    }
                }
            }
        }
        
    }
    
}
class Coordinate{
    int x;
    int y;
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}