[백준] 7576 : 토마토 - Java

• 백준 문제 URL

---

문제 요약

(M times N) 크기의 상자에 토마토가 들어있고, 익은 토마토(1)는 하루가 지나면 상하좌우의 익지 않은 토마토(0)를 익게 만든다
모든 토마토가 익을 때까지의 최소 날짜를 출력하고, 끝까지 익지 못하는 토마토가 있으면 -1을 출력한다.
처음부터 모두 익어있다면 0을 출력한다.

---

핵심 아이디어

최소 날짜를 구하는 문제는 “동시에 퍼져나가는 최단 거리” 구조이므로 BFS가 정답이다.
특히 이 문제는 시작점(익은 토마토)이 여러 개일 수 있으므로, 멀티 소스 BFS로 처음부터 익은 토마토 좌표를 전부 큐에 넣고 시작한다.
이후 box[nx][ny] = box[x][y] + 1 형태로 날짜를 누적 저장하면, 마지막에 최댓값에서 1을 빼서 최소 날짜를 얻을 수 있다.

---

알고리즘 핵심 로직

• 입력을 받으면서 값이 1인 좌표(처음부터 익은 토마토)를 전부 큐에 넣는다.
• 큐에서 하나씩 꺼내 4방향을 탐색하며, 범위 내이고 값이 0(안 익음)이면 현재값 + 1로 갱신하고 큐에 넣는다.
• BFS 종료 후 상자를 다시 훑어서 0이 남아있으면 익지 못한 토마토가 있는 것이므로 -1 출력한다
• 그렇지 않다면 상자 값의 최댓값 max를 구해 max - 1을 출력한다. (시작 익은 토마토가 1부터 시작했기 때문)

---

전체 코드(제출용)

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

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

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

        Queue<int[]> q = new ArrayDeque<>();

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

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

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int x = current[0];
            int y = current[1];

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

                if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    if (box[nx][ny] == 0) {
                        box[nx][ny] = box[x][y] + 1;
                        q.add(new int[]{nx, ny});
                    }
                }
            }
        }

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

        System.out.println(max - 1);
    }
}