Java : 토마토(BFS)

문제

풀이

1. 처음 입력받을 때 1(익은 토마토)인 좌표를 큐에 넣어준다.
2. 큐에서 좌표를 꺼내고 상하좌우 0(안 익은 토마토)인 좌표를 큐에 추가한다.
3. 추가하면서 대상 좌표에 '현재 좌표 값 + 1'(일 수)을 대입한다.

전체 코드

package inflearn;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class I0812 {
  static int ans = 0, m, n;
  static int[] dx = {-1, 0, 1, 0};
  static int[] dy = {0, 1, 0, -1};
  static int[][] board;
  static Queue<PointI0812> queue;

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    m = sc.nextInt();
    n = sc.nextInt();
    board = new int[n][m];
    queue = new LinkedList<>();

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        int status = sc.nextInt();
        board[i][j] = status;
        if (status == 1) queue.offer(new PointI0812(i, j));
      }
    }

    System.out.println(bfs());
  }

  static int bfs() {
    while (!queue.isEmpty()) {
      PointI0812 cur = queue.poll();
      for (int i = 0; i < 4; i++) {
        int row = cur.getX() + dx[i];
        int col = cur.getY() + dy[i];

        if (row >= 0 &&
            col >= 0 &&
            row < n &&
            col < m &&
            board[row][col] == 0) {
          queue.offer(new PointI0812(row, col));
          board[row][col] = board[cur.getX()][cur.getY()] + 1;
        }
      }
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (board[i][j] == 0) return -1;
        ans = Math.max(ans, board[i][j]);
      }
    }

    return ans - 1;
  }
}

class PointI0812 {
  private final int x;
  private final int y;

  public PointI0812(int x, int y) {
    this.x = x;
    this.y = y;
  }

  public int getX() {
    return x;
  }

  public int getY() {
    return y;
  }
}