[백준] 토마토 (7576번)

문제 흐름

1. 문제 목표
   • 상자에 있는 토마토들이 모두 익는 데 걸리는 최소 일수를 구합니다.
   • 토마토는 익은 상태에서 인접한 상하좌우의 토마토들을 하루마다 익게 만듭니다.
   • 모든 토마토가 익을 수 없는 경우 -1을 출력합니다.
2. 입력 설명
   • 첫 줄에 MMM (상자의 세로 크기)와 NNN (가로 크기) 입력.
   • 그다음 각 칸의 상태(익은 토마토: 1, 익지 않은 토마토: 0, 빈 칸: -1)로 상자를 초기화합니다.
3. 출력 설명
   • 모든 토마토가 익는 데 걸린 최소 일수를 출력.
   • 익지 못하는 토마토가 있다면 -1을 출력합니다.

 

핵심 아이디어

• BFS(너비 우선 탐색) 사용: 여러 위치에서 동시에 확산되는 문제이므로 BFS가 적합합니다.
• 큐(Queue)를 활용하여 여러 익은 토마토를 동시에 처리하며, 매일 새로운 익은 토마토를 큐에 추가합니다.
• 익지 않은 토마토가 남아 있는지 체크: 모든 토마토가 익었는지 확인해야 합니다.

 

알고리즘 흐름

1. 입력값 처리 및 초기화
   • 입력받은 토마토 상태를 2차원 배열에 저장.
   • 처음부터 익은 토마토(1인 위치)를 큐에 넣어 BFS를 시작할 준비를 합니다.
2. BFS로 확산
   • 큐에 있는 모든 익은 토마토에서 하루 동안 인접한 토마토를 익힙니다.
   • 모든 탐색이 끝나면 전체 경과 일수를 반환합니다.
3. 모든 토마토가 익었는지 검사
   • BFS가 종료된 후, 익지 않은 토마토가 남아 있는지 확인합니다.
   • 익지 않은 토마토가 있으면 -1을, 그렇지 않으면 경과 일수를 출력합니다.

 

---

정답은 더보기 클릭

import java.util.*;

public class Main {

    static int N;  // 상자의 가로 크기
    static int M;  // 상자의 세로 크기
    static int[][] map;  // 토마토 상태를 저장하는 2차원 배열

    // 상하좌우 방향으로 이동하기 위한 배열
    static final int[] dx = {1, -1, 0, 0};
    static final int[] dy = {0, 0, 1, -1};

    static Scanner in;  // 입력을 처리하는 Scanner
    static Queue<int[]> q = new LinkedList<>();  // BFS를 위한 큐

    public static void main(String[] args) {
        in = new Scanner(System.in);

        // 상자 크기 입력
        N = in.nextInt();
        M = in.nextInt();

        // 토마토 상자 초기화
        initMap();

        // BFS 실행 및 결과 계산
        int result = bfs();

        // 모든 토마토가 익었는지 확인하고 결과 출력
        System.out.println(allRipenTomatoes() ? result : -1);
    }

    // BFS를 사용해 토마토가 익어가는 일수를 계산하는 메서드
    public static int bfs() {
        int days = -1;  // 경과 일수 초기화

        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {
            int size = q.size();  // 현재 큐의 크기(오늘 익을 토마토 수)
            days++;  // 하루 경과

            // 오늘 익은 토마토들 처리
            for (int i = 0; i < size; i++) {
                int[] tmp = q.poll();  // 큐에서 하나의 토마토 좌표 꺼내기

                int x = tmp[0];  // 현재 토마토의 행
                int y = tmp[1];  // 현재 토마토의 열

                // 상하좌우로 인접한 토마토를 탐색
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j];  // 새로운 행 좌표
                    int ny = y + dy[j];  // 새로운 열 좌표

                    // 상자의 범위 안에 있고, 익지 않은 토마토(0)일 경우
                    if (nx >= 0 && ny >= 0 && nx < M && ny < N && map[nx][ny] == 0) {
                        map[nx][ny] = 1;  // 토마토를 익게 만듦
                        q.add(new int[]{nx, ny});  // 새로운 익은 토마토를 큐에 추가
                    }
                }
            }
        }

        return days;  // 모든 토마토가 익는 데 걸린 일수 반환
    }

    // 모든 토마토가 익었는지 확인하는 메서드
    public static boolean allRipenTomatoes() {
        // 상자 안의 모든 칸을 검사
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 0) return false;  // 익지 않은 토마토가 있으면 false 반환
            }
        }

        return true;  // 모든 토마토가 익었으면 true 반환
    }

    // 상자를 초기화하는 메서드
    public static void initMap() {
        map = new int[M][N];  // 상자 크기에 맞게 배열 생성

        // 각 칸의 상태를 입력받음
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = in.nextInt();  // 토마토 상태 입력

                // 익은 토마토(1)는 큐에 추가
                if (map[i][j] == 1) {
                    q.add(new int[]{i, j});
                }
            }
        }
    }

    // 상자의 상태를 출력하는 디버깅용 메서드
    public static void viewMap() {
        for (int[] arr : map) {
            System.out.println(Arrays.toString(arr));
        }
    }
}