[백준] 7576번 토마토

- 기억할 것

1. 익은 토마토가 있는 곳 =  행렬의 값이 1인 지점을 시작점으로 해야한다. >> 처음에 행렬 값이 1인 x,y 좌표를 먼저 저장한다.

2. 애초에 다 익은 경우 0을 출력, 다 익지 못하는 경우 -1을 출력

3. 익은 토마트 = 안익은 토마토 + 1

4. 현재 있는 위치가 (x,y) 라면 그 다음 갈 수 있는 좌표는 인접해 있는 상,하,좌,우 칸입니다. 즉, 상 : (x-1,y) , 하 : (x+1,y), 좌 : (x,y-1), 우 : (x, y+1) 이므로 이를 4개의 순서쌍으로 생각해서 배열로 만들 수 있다. 

package baekjun;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
class Coordinate{
    int x;
    int y;
    
    Coordinate(int x, int y){
        this.x = x;
        this.y = y;
    }
}
 
public class baekjun7576 {
    static int n;
    static int m;
    static int[][] matrix;
    static int[][] tomato;
    static Queue<Coordinate> q = new LinkedList<Coordinate>();
    
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    
    private static void BFS() {
        // TODO Auto-generated method stub
        while(!q.isEmpty()) {
            Coordinate c = q.poll();
            int x = c.x;
            int y = c.y;
 
            for(int k=0; k<4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                
                if(nx >= 0 && ny >= 0 && nx<n && ny<m) {
                    if(matrix[nx][ny] == 0 && tomato[nx][ny]==-1) {
                        matrix[nx][ny] = 1;
                        tomato[nx][ny] = tomato[x][y] + 1;
                        q.add(new Coordinate(nx,ny));
                    }
                }
            }
        }
    }
    
    private static void lastCheck() {
        // TODO Auto-generated method stub
        int rs = 1;
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(matrix[i][j] == 0) {
                    System.out.println("-1");
                    return;
                }
                
                if(tomato[i][j] > rs) {
                    rs = tomato[i][j];
                }
            }            
        }
        System.out.println(rs);
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        boolean check = false;
        
        n = sc.nextInt(); //행
        m = sc.nextInt(); //열
        
        matrix = new int [n][m];
        tomato = new int[n][m];
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                matrix[i][j] = sc.nextInt();
                tomato[i][j] = -1;
                
                if(matrix[i][j]==1) {
                    tomato[i][j] = 0;
                    q.add(new Coordinate(i,j));
                }
                
                if(matrix[i][j]==0 && check) {
                    check = true;
                }
            }
        }
        
        if(check) System.out.println(0);
        else {
            BFS();
            lastCheck();
        }
    }
}