처음에는 단순하게 익은 토마토에서부터 BFS를 돌면서 count를 1씩 증가시키면 된다고 생각했었는데, 처음에 익은 토마토가 여러 개일 경우 이 방법은 사용할 수 없었다.
그래서 두번째로 생각한 방법은 BFS를 할 때 익은 토마토를 모두 큐에 넣고 시작하는 거 였는데 결국 이 방법도 첫번째와 다를게 없었다.

그래서 생각해낸 방법은 bfs를 돌면서 count를 증가시키는 것이 아니라 bfs를 돌면서 해당 노드에 그 전 노드의 값 +1을 해주는 것이었다.

풀이

1. time, map 배열을 선언하고 map에 입력값을 저장한다.
2. time 배열은 0으로 전부 초기화하고, map에 저장하면서 익은 토마토가 저장될 경우 큐에 추가하고 time 배열의 해당 좌표를 1로 초기화한다.
3. map이 0인 부분 즉, 익지 않은 토마토가 있는 부분은 -1로 초기화한다.
4. bfs를 돌면서 익지 않은 토마토일 경우 직전 토마토의 time+1값으로 초기화한다.
5. BFS를 전부 돌면, 이중반복문으로 time에 -1인 부분이 있는지 확인하고 있으면 -1, 없으면 result를 출력한다.

코드

package BOJ;

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

public class sol7576 {

    static int N, M;
    static int[][] map;
    static int[][] time;
    static Queue<Point> tomato;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int result = 0;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        time = new int[N][M];
        tomato = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) tomato.add(new Point(i, j));
                if(map[i][j]==0) time[i][j] = -1;
            }
        }

        bfs();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (time[i][j] == -1) {
                    System.out.println(-1);
                    return;
                }
                result = Math.max(result, time[i][j]);
            }
        }
        System.out.println(result);

    }

    public static void bfs() {

        while (!tomato.isEmpty()) {
            Point t = tomato.poll();
            for (int i = 0; i < 4; i++) {
                int newX = t.x + dx[i];
                int newY = t.y + dy[i];
                if ((newX >= 0 && newX < N) && (newY >= 0 && newY < M)) {
                    if (map[newX][newY] == 0 && time[newX][newY] == -1) {
                        tomato.add(new Point(newX, newY));
                        time[newX][newY] = time[t.x][t.y] + 1;
                    }
                }
            }
        }


    }

    public static class Point {
        int x, y;

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

리뷰

BFS 알고리즘을 사용할 때 이런식으로 특정 값을 채우는 것이 아닌 거리 등을 계산할 때는 배열의 값을 업데이트하는 방식을 사용하면 좋겠다는 것을 알게되었다.