[BOJ 백준] 7576 - 토마토, Java(자바)

문제

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

7576번: 토마토

풀이

다음 날 익을 토마토를 큐에 담고, 남은 토마토가 없거나 더 이상 토마토가 익지 않을 때까지 bfs를 이용해 탐색한다.

코드

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

public class Main {
    public static void main(String args[]) throws Exception {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int M = Integer.parseInt(st.nextToken());
      int N = Integer.parseInt(st.nextToken());
      int[][] box = new int[N][M];
      int cnt = 0;
      Queue<int[]> queue = new LinkedList<int[]>();
      for (int i = 0; i < N; i++) {
          st = new StringTokenizer(in.readLine());
          for (int j = 0; j < M; j++) {
            box[i][j] = Integer.parseInt(st.nextToken());
            if (box[i][j] == 0)
                cnt++;
            else if (box[i][j] == 1)
                queue.offer(new int[] {i, j});
          }
      }
      int day = 0;
      int[][] delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
      outer:
      while(cnt > 0 && !queue.isEmpty()) {
          int size = queue.size();
          for (int s = 0; s < size; s++) {
              int r = queue.peek()[0];
              int c = queue.poll()[1];
              for (int d = 0; d < delta.length; d++) {
                  int dr = r + delta[d][0];
                  int dc = c + delta[d][1];
                  if (dr < 0 || dc < 0 || dr >= N || dc >= M || box[dr][dc] != 0)
                    continue;
                  if (--cnt == 0) {
                      ++day;
                      break outer;
                  }
                  box[dr][dc] = 1;
                  queue.offer(new int[] {dr, dc});
              }
          }
          day++;
      }
      System.out.println(cnt == 0 ? day : -1);
    }
}