[백준] 7569번 Java (그래프, bfs)

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

문제

풀이

접근법 : 3차원 배열의 상자에 토마토가 있다.

배열에 넣을 때 box[h][n][m] 으로 넣는다.
높이 h, 세로 n = 행렬의 행, 가로 m = 행렬의 열

BFS를 통해 6방향으로 익은 토마토가 있는지 확인하고, 안 익은 토마토는 익힌다.

아직 익지 않은 토마토가 있으면 -1, 모든 토마토가 익었다면 날짜를 출력한다.

• bfs 풀이 부분

 static int bfs(Queue<int[]> queue) {
        int days = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int z = current[0];
                int y = current[1];
                int x = current[2];
                // 6방향 탐색
                for (int j = 0; j < 6; j++) {
                    int nz = z + dz[j];
                    int ny = y + dy[j];
                    int nx = x + dx[j];
                    // 경계 설정 및, 근처에 있는 안 익은 토마토의 경우
                    if (nz >= 0 && ny >= 0 && nx >= 0 && nz < h && ny < n && nx < m && box[nz][ny][nx] == 0) {
                        box[nz][ny][nx] = 1;    // 익힌다.
                        queue.add(new int[]{nz, ny, nx});
                    }
                }
            }
            if (!queue.isEmpty()) days++;   // 날짜를 추가한다.

        }
        return days;
    }

• bfs를 계속 풀다보니 풀이 부분은 거의 비슷하다.
• 입력 시 Queue를 생성해서 익은 토마토는 미리 담아주었다.
• days를 체크해준다.
• x,y,z 좌표를 6방향 탐색해준다.
• 토마토 상자의 경계를 설정해주고, 안익은 토마토를 찾아 익힌 뒤 큐에 넣어준다.
• while문이 끝나도 큐가 다 비워지지 않았다면(익힐 토마토가 남아있다면) 하루가 지났음을 표시한다.
• 큐가 비어 있으면 BFS 탐색이 종료된다.

내 코드

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

public class Main {
    static int[][][] box;
    static int[] dx = {1, 0, -1, 0, 0, 0};
    static int[] dy = {0, 1, 0, -1, 0, 0};
    static int[] dz = {0, 0, 0, 0, 1, -1};
    static int n, m, h;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());
        box = new int[h][n][m];
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < n; j++) {   //y값
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < m; k++) {   //x값
                    box[i][j][k] = Integer.parseInt(st.nextToken());
                    if (box[i][j][k] == 1) {    //익은 토마토
                        queue.add(new int[]{i, j, k});  //바로 queue에 넣기
                    }
                }
            }
        }

        int result = bfs(queue);

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (box[i][j][k] == 0) {    // 만약 익지 않은 토마토가 있다면
                        System.out.println(-1);
                        return;
                    }
                }
            }
        }
        System.out.println(result);
    }

    static int bfs(Queue<int[]> queue) {
        int days = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int z = current[0];
                int y = current[1];
                int x = current[2];
                // 6방향 탐색
                for (int j = 0; j < 6; j++) {
                    int nz = z + dz[j];
                    int ny = y + dy[j];
                    int nx = x + dx[j];
                    // 경계 설정 및, 근처에 있는 안 익은 토마토의 경우
                    if (nz >= 0 && ny >= 0 && nx >= 0 && nz < h && ny < n && nx < m && box[nz][ny][nx] == 0) {
                        box[nz][ny][nx] = 1;    // 익힌다.
                        queue.add(new int[]{nz, ny, nx});
                    }
                }
            }
            if (!queue.isEmpty()) days++;   // 날짜를 추가한다.

        }
        return days;
    }
}