백준 - 7569

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

public class Main {
    static int[][][] tomato;
    static boolean[][][] visited;
    static int[][] dir = {
            {0, 1, 0},  
            {0, -1, 0},  
            {0, 0, 1}, 
            {0, 0, -1},  
            {1, 0, 0},   
            {-1, 0, 0}   
    };
    static int M, N, Z;

    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());
        Z = Integer.parseInt(st.nextToken()); 

        tomato = new int[Z][N][M];
        visited = new boolean[Z][N][M];

        List<int[]> list = new ArrayList<>();
        for(int k = 0; k < Z; k++) {
            for(int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < M; j++) {
                    int a = Integer.parseInt(st.nextToken());
                    tomato[k][i][j] = a;
                    if(a == 1) list.add(new int[]{k, i, j});
                }
            }
        }
        System.out.println(bfs(list));
    }

    static int bfs(List<int[]> list) {
        int cnt = -1;

        Queue<List<int[]>> all = new ArrayDeque<>();
        all.offer(list);

        while(!all.isEmpty()) {
            List<int[]> after = all.poll();
            List<int[]> put = new ArrayList<>();

            for(int[] a : after) {
                int z = a[0], x = a[1], y = a[2];
                visited[z][x][y] = true;

                for(int d = 0; d < 6; d++) {
                    int nz = z + dir[d][0];
                    int nx = x + dir[d][1];
                    int ny = y + dir[d][2];

                    if(nz >= 0 && nx >= 0 && ny >= 0 && nz < Z && nx < N && ny < M
                            && tomato[nz][nx][ny] == 0 && !visited[nz][nx][ny]) {
                        tomato[nz][nx][ny] = 1;
                        visited[nz][nx][ny] = true;
                        put.add(new int[]{nz, nx, ny});
                    }
                }
            }

            if(!put.isEmpty()) all.offer(put);
            cnt++;
        }
        for(int k = 0; k < Z; k++) {
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < M; j++) {
                    if(tomato[k][i][j] == 0) return -1;
                }
            }
        }
        return cnt;
    }
}

풀이과정 및 리뷰

• 문제 접근:
  • 토마토는 익은 토마토들(1)이 동시에 bfs탐색해야되므로, bfs를 쓸때 1인 것들을 모두 찾아 동시에 큐에 집어넣고 탐색이 끝나면 cnt++, 다음 1인 노드들 탐색하는 식으로 풀어야겠다고 생각함
  • bfs탐색이 끝난후에는 tomato배열을 탐색해 0을 마주치는 순간 바로 -1을 리턴하도록 함
• 시간복잡도: $O(Z * M * N)$
• 풀이과정
  • tomato / visited 3차원 배열 생성 및 델타(2차원배열로 3차원 표현) 선언
  • tomato 배열을 채우면서 입력값이 1이라면 따로 리스트에 i/j/k 저장 → if(a == 1) list.add(new int[]{k, i, j});
    
  • 리스트를 인자로 받는 bfs메서드 선언
    • 큐 두개 생성
      • 바깥 큐 : 익은 토마토(1)을 동시에 순회하기 위한 큐 → Queue<List<int[]>> all = new ArrayDeque<>();
        
      • 안쪽 큐 : 익은 토마토 리스트들을 각각 순회하며 인접 4방향 탐색

        • 이때, 방문하지않았고/인접노드값이 0이라면 1로 바꾸고 list에 넣음

          → `List<int[]> put = new ArrayList<>();` : 익은 토마토들의 인접 4방향 탐색해서 익힌 토마토들의 위치값들로, 익은 토마토들의 4방향 탐색이 끝나면(= 안쪽 큐가 비면)한꺼번에 바깥큐에 집어넣음
          
          이때, 리스트가 빈다면 더이상 바깥큐에 집어넣지않아서 큐를 비게 만든다.
          
          → `List<int[]> after = all.poll();` : 바깥큐에 집어넣은 익은 토마토들을 받음

          → 안쪽 큐를 순회하며 안쪽 큐가 빌경우 cnt++함( = 하루지남)

    • 모든 반복문이 종료된 후, tomato배열 전체를 탐색하며 0인값이 존재한다면 익지 않은 토마토가 존재하는 것이므로 -1 리턴하면서 종료, 그게 아니라면 날짜(cnt) 리턴하면서 종료
• 개선점

  • BFS에서 visited 처리 위치

    if(!visited[nr][nc][nz] && tomato[nr][nc][nz]==0){
        visited[nr][nc][nz] = true;
        tomato[nr][nc][nz] = 1;
        put.add(new int[]{nr,nc,nz});
    }

    벽(-1)이나 이미 익은 토마토(1)에 대해 visited가 먼저 체크됨 → 논리적으로 안전하지만, 배열 순서 꼬이면 BFS가 정상 작동 안 함

    → tomato==0 조건 안쪽에서 visited 체크 → 불필요한 visited 체크 방지

  • BFS 구조 개선 가능

    • 지금 BFS 구조: Queue<List<int[]>> all + 내부에서 또 Queue<int[]> q → 중첩 큐 구조

    • 개선: 단일 Queue<int[]> + level 크기만큼 for문 처리로 단순화 가능

      Queue<int[]> q = new ArrayDeque<>();
      int days = 0;
      
      while(!q.isEmpty()){
          int size = q.size();
          for(int s=0; s<size; s++){
              int[] cur = q.poll();
              // 6방향 전파
          }
          days++;
      }

  • cnt 처리 방식

    • 현재: cnt++ → BFS 반복마다 증가
    • 개선: level 단위 BFS에서 마지막 단계에서 증가하지 않도록 조정 → 실제 걸린 날짜 정확히 계산

  • 배열 순서 관련 개선

    • [Z][M][N] → 높이, 행, 열 순서로 통일하면 입력과 BFS, 델타 적용이 직관적 → 즉, 3차원 배열은 일반적으로 높이 / 행 / 열 순으로 작성함
      

  • 주요 개선점 : 복합 큐 쓸 필요가 없음. 단일 큐로 구현 가능