[백준] 토마토 (7569번)

코드 힌트

1. 자료 구조
   • 토마토 관리 : 상, 하, 좌, 우, 위, 아래를 관리하기 위해 3차원 배열을 사용
   • 상태 변화 : 이중 큐를 사용하여 이미 익은 토마토와 방금 익은 토마토를 관리
2. 핵심 로직
   • 그래프를 초기화(입력 받기) 시킵니다.
     • 이 때 익은 토마토(값이 1일 때)를 큐에 저장을 합니다.
   • 회차 별로 BFS를 시작합니다.
     • 익은 토마토로 인해 확산되어 익은 토마토는 또 다른 큐에 저장합니다
     • 기존의 큐에 저장을 하면 count를 제대로 할 수 없습니다.
   • BFS가 종료되었을 때 이제 막 익은 토마토 큐가 비어있는 지 확인합니다.
   • 만약 새롭게 익은 토마토가 없다면(큐가 비어있을 때) 그대로 종료합니다.
   • 새롭게 익은 토마토가 있다면 익은 토마토 큐에 저장을 하고 막 익은 토마토 큐를 비워줍니다.
   • 새롭게 익은 토마토가 없을 때 까지 반복하기
3. 조심해야 할 점
   • count를 증가시킬 때는 새롭게 익은 토마토가 있는지 확인 후 증가시켜야합니다.
   • 모든 BFS 회차가 종료되었을 때 익지 않은 토마토가 있는지 확인해야합니다.

 

---

정답은 더보기 클릭

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

public class Main {
    static Scanner in;

    static int N; // x축 크기
    static int M; // y축 크기
    static int F; // z축 크기 (층 수)

    static int[][][] graph; // 3차원 그래프를 표현하는 배열

    // 방향 벡터 (상, 하, 좌, 우, 위, 아래)
    static int[] dx = {1, -1, 0, 0, 0, 0};
    static int[] dy = {0, 0, 1, -1, 0, 0};
    static int[] dz = {0, 0, 0, 0, 1, -1};

    // 현재 익은 토마토의 위치를 담는 큐
    static final Queue<int[]> queue = new LinkedList<>();
    // 익게 될 토마토의 위치를 담는 큐
    static final Queue<int[]> changeQueue = new LinkedList<>();

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

        // 입력: 그래프 크기
        N = in.nextInt(); // x축 크기
        M = in.nextInt(); // y축 크기
        F = in.nextInt(); // z축 크기

        // 그래프 초기화 (입력받기)
        graphInit();

        int count = 0; // 모든 토마토가 익는 데 걸리는 일수

        // BFS 반복 수행
        while (true) {
            bfs(); // 현재 큐에 있는 토마토로 주변 익히기

            // 새로 익은 토마토가 없는 경우 종료
            if (changeQueue.isEmpty()) {
                break;
            }

            count++; // 하루 증가
            queue.addAll(changeQueue); // 새로 익은 토마토를 큐에 추가
            changeQueue.clear(); // 새로 익은 토마토 목록 초기화
        }

        // 결과 출력: 모든 토마토가 익었는지 확인
        if (isAllEven()) {
            System.out.println(count); // 모든 토마토가 익었을 때의 일수
        } else {
            System.out.println(-1); // 익지 않은 토마토가 남아있을 경우
        }
    }

    // 그래프 전체를 확인하여 익지 않은 토마토(값 0)가 있는지 체크
    public static boolean isAllEven() {
        for (int i = 0; i < F; i++) {
            for (int j = 0; j < M; j++) {
                for (int k = 0; k < N; k++) {
                    if (graph[i][j][k] == 0) { // 익지 않은 토마토 발견
                        return false;
                    }
                }
            }
        }
        return true; // 모든 토마토가 익음
    }

    // BFS를 수행하여 익지 않은 토마토를 익히는 과정
    public static void bfs() {
        while (!queue.isEmpty()) {
            int[] point = queue.poll(); // 현재 위치 가져오기

            int x = point[0];
            int y = point[1];
            int z = point[2];

            // 6방향 탐색 (상, 하, 좌, 우, 위, 아래)
            for (int i = 0; i < 6; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int nz = z + dz[i];

                // 새로운 위치가 익힐 수 있는지 확인
                if (isAble(nx, ny, nz)) {
                    changeQueue.offer(new int[] {nx, ny, nz}); // 새로 익은 토마토 추가
                    graph[nx][ny][nz] = 1; // 토마토를 익음 상태로 변경
                }
            }
        }
    }

    // 주어진 위치가 범위 내에 있고 익힐 수 있는 상태인지 확인
    public static boolean isAble(int x, int y, int z) {
        return x >= 0 && y >= 0 && z >= 0 && x < F && y < M && z < N
                && graph[x][y][z] == 0; // 익지 않은 토마토만 익힐 수 있음
    }

    // 그래프 초기화 및 익은 토마토 초기 큐 세팅
    public static void graphInit() {
        graph = new int[F][M][N];

        for (int i = 0; i < F; i++) {
            for (int j = 0; j < M; j++) {
                for (int k = 0; k < N; k++) {
                    graph[i][j][k] = in.nextInt(); // 토마토 상태 입력
                    if (graph[i][j][k] == 1) { // 익은 토마토 위치를 큐에 추가
                        queue.offer(new int[] {i, j, k});
                    }
                }
            }
        }
    }
}