[백준] 7576번 - 토마토 문제 풀이 및 코드 해석 (Java)

문제 링크

---

1. 문제 분석

📌 문제 개요

• M x N 크기의 상자에 익은 토마토(1), 익지 않은 토마토(0), 빈 칸(-1)이 있다.
• 익은 토마토는 인접한 네 방향(상, 하, 좌, 우)으로 익지 않은 토마토를 하루에 한 번 익게 만든다.
• 모든 토마토가 익을 때까지 걸리는 최소 일수를 구해야 한다.
• 익지 않은 토마토가 존재하지만 익을 수 없는 경우에는 -1을 출력한다.
• 모든 토마토가 이미 익어 있다면 0을 출력한다.

🎯 요구사항

1. BFS(너비 우선 탐색) 을 활용하여 최소 일수를 구해야 한다.
2. 익은 토마토에서 BFS를 시작하여 인접한 익지 않은 토마토를 익게 만든다.
3. 익지 않은 토마토가 남아 있다면 -1을 출력해야 한다.

---

2. 해결 방법

🔹 핵심 개념

• BFS(너비 우선 탐색) 을 이용하여 최소 거리를 구하는 전형적인 문제
• 여러 개의 시작점(익은 토마토들)에서 동시에 탐색 시작
• BFS를 통해 익는 날짜를 1일씩 증가시키며 확산

🔑 해결 절차

1. 입력값 처리 및 BFS 초기화
   • board[N][M] → 토마토 상태 저장
   • score[N][M] → 토마토가 익는데 걸리는 일수 저장
   • visited[N][M] → 방문 여부 저장
   • 익은 토마토(1)를 BFS의 시작점으로 큐에 저장
2. BFS 수행 (최소 거리 탐색)
   • Queue를 사용하여 익은 토마토에서 BFS 탐색 진행
   • 익지 않은 토마토(0)를 발견하면 1일 추가하고 큐에 삽입
3. 결과 도출
   • 모든 토마토가 익었는지 확인
   • 익지 않은 토마토(0)가 남아 있으면 -1 출력
   • 모든 토마토가 익었다면 최댓값(최대 일수) 출력

---

3. 코드 구현

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

public class Main {
    static int M, N;
    static int[][] board, days;
    static int[] dr = {0, 0, 1, -1}; // 상, 하, 좌, 우 이동
    static int[] dc = {1, -1, 0, 0};
    static Queue<int[]> queue = new LinkedList<>();

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

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

        board = new int[N][M];
        days = new int[N][M];

        boolean allRipe = true; // 모든 토마토가 처음부터 익어있는지 체크
        boolean hasUnripe = false; // 익지 않은 토마토가 있는지 체크

        for (int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < M; c++) {
                board[r][c] = Integer.parseInt(st.nextToken());

                if (board[r][c] == 1) { // 익은 토마토 -> BFS 시작점
                    queue.add(new int[]{r, c});
                } else if (board[r][c] == 0) {
                    allRipe = false;
                    hasUnripe = true;
                }

                days[r][c] = (board[r][c] == 0) ? Integer.MAX_VALUE : 0; // 익지 않은 토마토는 최대값 초기화
            }
        }

        if (allRipe) {
            System.out.println(0); // 이미 모든 토마토가 익어있음
            return;
        }

        bfs();

        int maxDays = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                if (board[r][c] == 0) { // 익지 않은 토마토가 남아 있다면
                    System.out.println(-1);
                    return;
                }
                maxDays = Math.max(maxDays, days[r][c]);
            }
        }

        System.out.println(maxDays);
    }

    private static void bfs() {
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            int r = pos[0], c = pos[1];

            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];

                if (nr >= 0 && nr < N && nc >= 0 && nc < M && board[nr][nc] == 0) {
                    board[nr][nc] = 1; // 익은 토마토로 변경
                    days[nr][nc] = days[r][c] + 1;
                    queue.add(new int[]{nr, nc});
                }
            }
        }
    }
}

---

4. 코드 분석

🔹 주요 알고리즘

1. BFS를 활용한 최소 일수 탐색
   • 여러 개의 시작점(익은 토마토)에서 BFS 수행
   • 최소 거리 개념으로 익지 않은 토마토(0)를 익게 만듦
2. BFS를 통한 탐색 과정
   • Queue를 이용하여 익은 토마토의 위치를 저장
   • poll()을 이용하여 상하좌우로 확산
   • 익지 않은 토마토(0)를 발견하면 1일 증가
   • 모든 토마토가 익는 데 걸리는 최대 일수를 저장
3. 최종 결과 도출
   • 모든 토마토가 익었다면 maxDays 출력
   • 익지 않은 토마토가 남아 있으면 -1 출력

🔹 시간 복잡도 분석

• 입력 처리: O(N * M)
• BFS 탐색: O(N * M)
• 최종 검증: O(N * M)
• 총 시간 복잡도: O(N * M)
  • N, M ≤ 1000이므로 최대 1,000,000번 연산 → 충분히 해결 가능

---

5. 개선할 점 및 대체 방법

✅ 개선할 점

1. 배열을 방문 배열(visited) 없이 활용 가능
   • days[][]를 방문 여부로 활용하면 visited 배열 불필요
2. BFS 최적화
   • Deque를 활용하면 poll() 연산을 더 빠르게 수행 가능
3. 입력 최적화
   • BufferedReader를 사용하여 빠르게 입력 처리

🔄 대체 방법

1. DFS 활용 가능하지만, BFS가 최적
   • DFS는 깊이 우선 탐색이므로, 최소 거리 탐색에 적합하지 않음
2. Flood Fill 알고리즘 응용 가능
   • BFS를 활용하여 Flood Fill 방식을 적용 가능