[BJ] 7576 : 토마토

       문제 요약        

- 문제

https://www.acmicpc.net/problem/7576

 

 

 

- 입출력

토마토가 모두 익을 때까지의 최소 날짜 

output case : 저장될 때부터 모든 토마토가 익어있는 상태이면 0 출력, 모두 익지 못하는 상황이면 -1 출력, 그외 걸린 시간 출력  

 

         아이디어        

최소 날짜를 구해야 함

상태 변화가 단계의 어떤 영향을 끼치는지 주의깊게 봐야 함

         소스코드        

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
  static int M, N;
  static int WELL = 1, NOT_WELL = 0, NONE = -1;
  static int[][] box;
  static Queue<int[]> tomatos;
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    M = Integer.parseInt(st.nextToken());
    N = Integer.parseInt(st.nextToken());

    int notWellTomatoCnt = 0;
    tomatos = new ArrayDeque<>();
    box = new int[N][M];
    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < M; j++) {
        box[i][j] = Integer.parseInt(st.nextToken());
        if (box[i][j] == 1) {
          tomatos.add(new int []{i, j, 0});
        }
     
        if (box[i][j] == NOT_WELL) { // 안 익은 토마토
          notWellTomatoCnt += 1;
        }
      }
    }

    if (notWellTomatoCnt == 0) { // 모두 익은 토마토인 경우
      System.out.println(0);
      return;
    }

    int [][] way = {{1,0},{-1,0},{0,1},{0,-1}};
    int time = -1;
    while (!tomatos.isEmpty()) { // 토마토 익히기 
      int[] now = tomatos.poll();
      time = now[2];
      for(int w = 0; w < 4; w++) {
        int nx = way[w][0] + now[0];
        int ny = way[w][1] + now[1];
        if (nx < 0 || nx>=N || ny < 0 || ny >= M)continue;
        if (box[nx][ny] == NOT_WELL) { // 가지치기 
          tomatos.add(new int[]{nx,ny, now[2] + 1});
          box[nx][ny] = WELL;
          notWellTomatoCnt -= 1;
        }
      }
    }
    
    if (notWellTomatoCnt != 0) { // 안 익은 토마토가 있다면 
      time = -1;
    }
    
    System.out.println(time);
  }
}