Baekjoon | Q.7576 - 토마토

7576번: 토마토

익은 토마토와 인접한 토마토는 하루의 시간이 지나면 익게 된다. 박스에 토마토가 전부 익는데 걸리는 시간을 구하는 문제이다.

 

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

class Main {
  static int N;
  static int M;
  static int[][] tomatos;

  static int[] dx = {-1, 0, 1, 0};
  static int[] dy = {0, 1, 0, -1};

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    M = sc.nextInt();
    N = sc.nextInt();
    tomatos = new int[N][M];

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        tomatos[i][j] = sc.nextInt();
      }
    }

    sc.close();
    bfs();
    // print(toamatos);
    int days = checkTomato();
    System.out.println(days);
  }

  static void bfs() {
    Queue<Integer> qx = new ArrayDeque<>();
    Queue<Integer> qy = new ArrayDeque<>();

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        if(tomatos[i][j] == 1) {
          qx.add(i);
          qy.add(j);
        }
      }
    }

    while(!qx.isEmpty() && !qy.isEmpty()) {
      int x = qx.poll();
      int y = qy.poll();

      for (int i = 0; i < 4; i++) {
        int _x = x + dx[i];
        int _y = y + dy[i];

        if(_x >= 0 && _y >= 0 && _x < N && _y < M) {
          if(tomatos[_x][_y] == 0) {
            qx.add(_x);
            qy.add(_y);
            tomatos[_x][_y] = tomatos[x][y] + 1;
          }
        }
      }
    }


  }

  static int checkTomato() {
    int max = 0;

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        if(tomatos[i][j] == 0) return -1;	// 안 익은 토마토가 있으면 -1 반환
        max = Math.max(max, tomatos[i][j]);	// 최댓값 갱신
      }
    }
    return max - 1;	// 0일째가 1일로 계산되어서 -1 처리해줌
  }

  static void print(int[][] arr) {	// 출력용
    for (int i = 0; i < arr.length; i++) {
      for (int j = 0; j < arr[0].length; j++) {
        System.out.print(arr[i][j] + " ");
      }
      System.out.println();
    }
  }
}

 

 인접한 토마토들이 차례로 익어가는 과정을 거치므로 BFS를 이용하여 풀었다. 다른 사람들의 풀이를 살펴보니 큐를 두 개를 생성하지 않고 x와 y를 멤버변수로 가지는 클래스를 따로 생성하여 하나의 큐로 구현하는 방법도 있었다.