99클럽 코테 스터디 12일차 TIL - BFS의 '동시' 탐색

문제

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

오늘의 학습 키워드

BFS 탐색으로 서로 다른 좌표에서 '동시에'  탐색이 처리된다는 것의 의미는 무엇일까?

공부한 내용 본인의 언어로 정리하기

해결 과정

문제의 핵심은 서로 다른 공간에 있는 익은 토마토들이 주변의 토마토들에 영향을 주며 하루씩 익어 가는 것을 어떻게 코드로 구현하냐는 것이라고 생각한다. 문제의 풀이법이 BFS로 접근해야 한다는 것은 쉽게 떠올릴 수 있었는데 익은 토마토들이 '동시에' 주변의 안 익은 토마토에 영향을 주게끔 코드를 구현하는 방법을 잘 떠올리지 못했다.

 

그래서 처음에는 days라는 3차원 배열을 만들고 각각의 익은 토마토에 대해 bfs를 실시하며 익는데까지 걸린 날을 갱신해주는 코드로 구현했다. 

1. 먼저 days라는 3차원 배열을 정수형의 최대 값으로 초기화한다.
2. 익은 토마토를 만나면 bfs를 실시하는데 실시할 때 토마토 저장 배열을 복사한 배열을 전달한다. 
3. bfs에서는 days 배열을 갱신하는데 queue에서 꺼낸 토마토의 익는데 까지 걸린 날이 days의 해당 인덱스의 값보다 작으면 그 날로 갱신한다.
4. 탐색이 모두 끝나면 days 배열에서 가장 큰 값(Integer.MAX_VALUE가 아닌)을 출력한다.

이렇게 구현했을 때 문제에서 제시된 케이스는 모두 통과했지만 실제 제출 시에는 시간초과가 발생했다. 모든 익은 토마토에 대해 bfs를 실시한다는 점과 배열을 복사하니 그만큼 시간이 더 걸리는 것으로 생각했다. 

'동시에' 익어가는 것이란

사실 아이디어는 간단했다. Queue에 처음부터 익은 토마토의 좌표(또는 노드)를 모두 넣고 BFS를 실시하면 된다.  

아래 이미지는 3 x 3 2차원 배열을 예시로 익은 토마토를 모두 넣고 BFS가 수행되는 과정을 표시한 것이다.

수행 과정을 보면 알겠지만 (0,0), (2,2) 를 모두 큐에 넣고 시작함으로써 동시에 주변 토마토가 익어가는 과정을 나타낼 수 있게 된다. 이 예시를 3차원 배열로 확장하면 된다.

 

아래는 전체 코드이다.

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

public class Main {

    static int N;
    static int M;
    static int H;

    // 위 아래 왼쪽 오른쪽 앞 뒤
    static int[] dx = new int[]{0, 0, -1, 1, 0, 0};
    static int[] dy = new int[]{0, 0, 0, 0, 1, -1};
    static int[] dz = new int[]{-1, 1, 0, 0, 0, 0};

    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());

        int[][][] arr = new int[H][N][M];
        boolean isAllOld = true;

        for(int h = 0; h < H; h++){
            for(int n = 0; n < N; n++){
                st = new StringTokenizer(br.readLine());
                for(int m = 0; m < M; m++){
                    int isOld = Integer.parseInt(st.nextToken());
                    if(isOld == 0){
                        isAllOld = false;
                    }
                    arr[h][n][m] = isOld;
                }
            }
        }

        if(isAllOld){
            System.out.println(0);
            return;
        }

        int[][][] visited = new int[H][N][M];
        int answer = bfs(arr, visited);

        boolean isCantOld = false;
        for(int h = 0; h < H; h++){
            for(int n = 0; n < N; n++){
                for(int m = 0; m < M; m++){
                    if(arr[h][n][m] == 0){
                        isCantOld = true;
                        break;
                    }
                }
                if(isCantOld) break;
            }
            if (isCantOld) break;
        }
        if(isCantOld) {
            System.out.println(-1);
            return;
        }

        System.out.println(answer);
    }

    static int bfs(int[][][] store, int[][][] visited){

        Queue<Point> queue = new LinkedList<>();
        for(int h = 0; h < H; h++){
            for(int n = 0; n < N; n++){
                for(int m = 0; m < M; m++){
                    if(store[h][n][m] == 1){
                        queue.add(new Point(h, n, m, 0));
                    }
                }
            }
        }

        int maxDay = 0;

        while (!queue.isEmpty()){
            Point point = queue.poll();

            maxDay = Math.max(maxDay, point.day);

            if(store[point.z][point.y][point.x] != 1){
                continue;
            }

            for(int d = 0; d < 6; d++){
                int dh = point.z + dz[d];
                int dn = point.y + dy[d];
                int dm = point.x + dx[d];

                if(dh < 0 || dh >= H){
                    continue;
                }
                if(dn < 0 || dn >= N){
                    continue;
                }
                if(dm < 0 || dm >= M){
                    continue;
                }

                if(store[dh][dn][dm] == 0 && visited[dh][dn][dm] == 0){
                    store[dh][dn][dm] = 1;
                    Point neighbor = new Point(dh, dn, dm, point.day + 1);
                    queue.add(neighbor);
                    visited[dh][dn][dm] = 1;
                }
            }
        }
        return maxDay;
    }

    static class Point{
        int z;
        int y;
        int x;

        int day;

        Point(int z, int y, int x, int day){
            this.z = z;
            this.y = y;
            this.x = x;
            this.day = day;
        }
    }
}

오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지
  
  • 처음 작성한 코드가 시간초과에 걸림
• 어떻게 해결했는지
  • BFS를 다시 생각하며 동시에 토마토가 익는 과정을 구현하려고 노력
• 무엇을 새롭게 알았는지
  • BFS를 통해 그래프 탐색 시 서로 다른 노드에서 동시에 탐색을 수행하는 방법에 대해 알게 됨
• 내일 학습할 것은 무엇인지