섹션 8 DFS, BFS - 12. 토마토(BFS 활용)

문제 설명

현수는 토마토를 보관하는 창고에서 익은 토마토가 익지 않은 토마토에 영향을 줘서 며칠 뒤 모든 토마토가 익는지를 알고 싶어한다.
격자 형태의 창고에서 하루마다 익은 토마토가 인접한 칸의 익지 않은 토마토를 익게 한다.

창고는 N행 M열로 구성되어 있으며 각 칸은 다음 중 하나이다:

• 1: 익은 토마토
• 0: 익지 않은 토마토
• -1: 토마토가 없는 칸

모든 토마토가 익기까지의 최소 일수를 구하라.
모든 토마토가 처음부터 익어 있으면 0,
절대 익지 못하는 토마토가 존재하면 -1을 출력한다.

---

입력 & 출력

입력

• 첫 줄에 M(가로), N(세로) (2 ≤ M, N ≤ 1,000)
• 다음 N줄에 M개의 정수 (토마토 상태)

출력

• 최소 일수 (불가능한 경우는 -1)

예시

입력:
6 4
0 0 -1 0 0 0
0 0 1 0 -1 0
0 0 -1 0 0 0
0 0 0 0 -1 1

출력:
4

---

해결 방법

• 이 문제는 여러 개의 익은 토마토(1) 에서 동시에 BFS 탐색을 시작해야 하므로 Multi-Source BFS 로 해결한다.
• 큐에 익은 토마토의 좌표를 모두 먼저 넣고, BFS를 돌리면 날짜(dis)를 1일씩 늘려가며 확산시킬 수 있다.
• 모든 토마토가 익는 데 걸린 최대 날짜(dis[x][y]) 를 정답으로 출력한다.
• BFS 이후에도 0이 남아 있다면 익지 못한 토마토가 있으므로 -1을 출력한다.

---

코드 구현

package partDfsBfs;

import java.util.*;

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

public class Problem12 {
    static int[] dx = {-1, 0, 1, 0}; // 상우하좌
    static int[] dy = {0, 1, 0, -1};
    static int n, m;
    static int[][] board, dis;
    static Queue<Point> Q = new LinkedList<>();

    public void BFS() {
        while (!Q.isEmpty()) {
            Point tmp = Q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] == 0) {
                    board[nx][ny] = 1;
                    Q.offer(new Point(nx, ny));
                    dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
                }
            }
        }
    }

    public static void main(String[] args) {
        Problem12 T = new Problem12();
        Scanner kb = new Scanner(System.in);
        m = kb.nextInt();
        n = kb.nextInt();
        board = new int[n][m];
        dis = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] = kb.nextInt();
                if (board[i][j] == 1) Q.offer(new Point(i, j)); // 초기 익은 토마토들
            }
        }

        T.BFS();

        boolean flag = true;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 0) flag = false;
            }
        }

        int answer = Integer.MIN_VALUE;
        if (flag) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    answer = Math.max(answer, dis[i][j]);
                }
            }
            System.out.println(answer);
        } else {
            System.out.println(-1);
        }
        kb.close();
    }
}

---

코드 설명

• Point 클래스: 현재 좌표 저장
• Q: 익은 토마토들의 위치를 큐에 저장하여 동시에 BFS 수행
• dis[x][y]: (x,y) 위치가 익는 데 걸린 일수 저장
• board[x][y] = 1: 익었음을 표시하고 다시 방문하지 않게 함

---

시간 복잡도

• 격자 크기: N x M
• BFS는 각 칸을 최대 1번 방문
• 시간복잡도: O(N × M)
  → 입력 최대 크기 1,000 × 1,000 = 1,000,000 → 충분히 처리 가능

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런