[백준] 7576 토마토

문제보기

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

// 좌표를 나타낼 클래스
class Pair{
  int x;
  int y;
  Pair(int x, int y){
    this.x = x;
    this.y = y;
  }
}

// bfs 함수로 따로 안빼고(어차피 한번만 호출할거라) 메인메서드에서 구현
public class Main
{   
  public static int[][] d;
  public static int[] dx = {1, -1, 0, 0};
  public static int[] dy = {0, 0, 1, -1};
  public static int n;
  public static int m;
  public static int[][] map;

  public static void main(String[] args) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String[] line = bf.readLine().split(" ");
    m = Integer.valueOf(line[0]);
    n = Integer.valueOf(line[1]);

    map = new int[n][m];
    d = new int[n][m];
    boolean already = true; // 이미 모든 토마토가 익었는지 확인할 변수
    Queue<Pair> q = new LinkedList<>();


    for(int i = 0 ; i < n ; i++ ){
      String[] line2 = bf.readLine().split(" ");
      for(int j = 0 ; j < m ; j++ ){
        map[i][j] = Integer.valueOf(line2[j]);
        if(map[i][j] == 0){ // 아직 익지 않은 토마토인 경우
          already = false; // 하나라도 안익은게 있다면 이건 false
          d[i][j] = -1; // 나중에 방문할거라고 표시
        }
        if(map[i][j] == 1){ // 이미 익은 토마토인 경우
          q.add(new Pair(i, j)); // 여기서부터 출발해야하므로 q에 저장한다
          d[i][j] = 0; // 방문할 필요가 없다고 표시
        }
      }
    }

    if(already){ // 혹시나 한번도 map[i][j] == 0 인 적이 없다면..
      System.out.println(0);
      return;
    }

 		// bfs
    while(!q.isEmpty()){
      Pair p = q.remove();
      int x = p.x;
      int y = p.y;

      for(int k = 0 ; k < 4 ; k++ ){
        int nx = x + dx[k];
        int ny = y + dy[k];

        // 일단 다음 지점이 지도 상에 존재해야 하고
        // 안익은 토마토가 있어야 하며
        // 방문한적이 없거나
        // 방문한 적이 있어도 지금 x, y에서 익어가는게 더 빠른 시일이라면 가야함
        if(nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] == 0 && (d[nx][ny] == -1 || d[nx][ny] > d[x][y]+1 )){
          d[nx][ny] = d[x][y] + 1;
          q.add(new Pair(nx,ny));
        }
      }
    }

    int ans = 0;
    for(int i = 0 ; i < n ; i++ ){
      for(int j = 0 ; j < m ; j++){
        if(d[i][j] == -1){ // 방문하지 못한 익지않은 토마토가 하나라도 있는지 확인
          System.out.println(-1);
          return;
        }
        if(ans < d[i][j]){ // 마지막에 익는 녀석은 며칠이 걸릴까?
          ans =  d[i][j];
        }
      }
    }
    System.out.println(ans);

  }
}