[BOJ/Gold5] 7569번 토마토 - JAVA[자바]

난이도 : 골드 5

유형 : BFS / 큐

링크 : https://www.acmicpc.net/problem/7569

구현 시간 : 1시간

 

 

 

 

 

 

 

문제풀이

1. 1. 토마토 박스를 3차원 배열에 저장한다.
   2. 1번 과정에서 빈칸의 개수, 익은 토마토의 개수를 저장한다.
      1. (총 배열의 크기 - 빈칸의 개수) 가 익은 토마토의 개수와 같다면 0 을 출력하고 종료한다.
   3. 익은 토마토가 있는 좌표를 Queue에 저장한다.
   4. Queue 가 비어있지 않을때까지 반복문 시작
      1. Queue의 현재 size 를 저장하고, size 만큼 for문을 돌린다.
         (BFS 탐색의 Depth를 기준으로 하루가 지남을 판별하기 위함)
      2. Queue에서 poll한 익은 토마토의 위치 기준 상하좌우아래위 6방향으로 탐색한다.
         1. 만약 탐색 위치가 박스 위치를 벗어나면, 다음 방향으로 넘어간다.
         2. 익지 않은 토마토가 있는 칸이라면, 해당 박스 위치에 익은 토마토로 변경하고 Queue에 새로운 좌표를 추가한다.
      3. BFS 탐색의 Depth를 반복하는 for문이 종료되면, Queue의 요소가 남아 있는지(탐색이 끝나지 않았는지) 확인하고, 요소가 남아있다면 날짜를 하루 더한다.
   5. BFS 가 종료되었다면, (익은 토마토의 수 + 빈칸의 개수)가 총 배열의 크기와 같은지 확인한다.
      1. 크기가 같지 않다면 토마토가 모두 익지 못하는 상황이므로 -1 을 출력하고 종료한다.
      2. 크기가 같다면 총 며칠이 지났는지(BFS의 depth)를 출력한다.

 

 

 

1차 시도 - 통과

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

public class Main {

    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};

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

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

        int[][][] box = new int[H][N][M];
        Queue<int[]> q = new LinkedList<>();

        int totalCount = M * N * H;
        int blankCount = 0;
        int ripeTomatoCount = 0;

        // 박스 상태 저장
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < M; k++) {
                    int status = Integer.parseInt(st.nextToken());
                    box[i][j][k] = status;

                    // 익은 토마토의 좌표 저장
                    if (status == 1) {
                        q.offer(new int[]{i, j, k});
                        ripeTomatoCount++;
                    }

                    // 빈칸 개수 저장
                    if (status == -1) {
                        blankCount++;
                    }
                }
            }
        }

        // 저장될 때부터 모든 토마토가 익어있는 상태이면 0 을 출력
        if (totalCount - blankCount == ripeTomatoCount) {
            System.out.println(0);
            return;
        }

        int day = 0;

        while (!q.isEmpty()) {
            int size = q.size();

            // BFS depth 레벨마다 반복
            for (int i = 0; i < size; i++) {
                int[] poll = q.poll();
                int z = poll[0];
                int x = poll[1];
                int y = poll[2];

                // 상하좌우밑위 탐색
                for (int j = 0; j < 6; j++) {
                    int nz = z + dz[j];
                    int nx = x + dx[j];
                    int ny = y + dy[j];

                    // 박스의 범위를 벗어난다면 즉시 종료
                    if (nz >= H || nx >= N || ny >= M || nz < 0 || nx < 0 || ny < 0) {
                        continue;
                    }

                    // 익지 않은 토마토 칸이라면 실행
                    if (box[nz][nx][ny] == 0) {
                        box[nz][nx][ny] = 1;
                        ripeTomatoCount++;
                        q.offer(new int[]{nz, nx, ny});
                    }
                }
            }

            if (!q.isEmpty()) {
                day++;
            }
        }

        // 토마토가 모두 익지는 못하는 상황이면 -1 출력
        if (ripeTomatoCount + blankCount != totalCount) {
            System.out.println(-1);
            return;
        }

        // 모두 익었다면 최소 일수 출력
        System.out.println(day);
    }
}