[JAVA] 백준 #7569 토마토🍅 버전2 | BFS | Queue | 예외처리 반례

[JAVA] 백준 #7569 토마토🍅 버전 2

7569번: 토마토

 

🔒 문제 설명

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

---

 🔐 1차 시도

우선 토마토 문제는 이전에 이미 풀이한 경험이 있다. 이 문제를 통해 처음으로 BFS를 완벽하게 이해하고 풀이할 수 있었는데 그때를 복기하며 수월하게 풀어나간 문제이다. 그때는 2차원 배열이었는데 이번에는 무려 3차원 배열이다. 

 

[JAVA] 백준 #7576 토마토🍅 | BFS 풀이 방법 | Deque와 Queue | 시간 초과 반례

 

bfs 원리나 자세한 풀이 방법은 이전 포스트에서 자세히 다뤘으니 생략하고 이번 포스트에선 내가 놓쳤던 예외 상황을 다뤄보려고 한다.

우선 내가 초반에 구현한 핵심 코드는 아래와 같다. 

 

1. for문을 돌면서 box 값이 1인 익은 토마토를 찾는다. 찾으면 바로 bfs 함수로 보내준다.

2. bfs 함수에서는 해당 토마토 위치를 기준으로 주위 여섯 방향을 순회하면서 익지 않은 토마토를 찾아 값을 누적해 간다.

 

이러한 로직으로 구성했는데 이는 틀린 풀이였다. 원인은 큐를 bfs 함수 안에 선언하고 함수 안에서 offer 한 것이 문제였다.

	// [2] bfs 실행
        for( int h = 0; h < H; h++ ){
            for( int n = 0; n < N; n++ ){
                for( int m = 0; m < M; m++ ){
                    if( box[h][n][m] == 1 && !visited[h][n][m] ){
                        bfs( m, n, h );
                    }
                }
            }
        }

...

    public static void bfs( int m, int n, int h ){
        Queue<int[]> queue = new LinkedList<>();

        queue.offer( new int[]{ m, n, h } );
        visited[h][n][m] = true;

        while(!queue.isEmpty()){
            int[] location = queue.poll();

            for( int i = 0; i < 6; i++ ){
                int nextM = location[0] + dm[i];
                int nextN = location[1] + dn[i];
                int nextH = location[2] + dh[i];

                if( nextM < 0 || nextM >= M || nextN < 0 ||
                        nextN >= N || nextH < 0 || nextH >= H ||
                        visited[nextH][nextN][nextM]) continue;

                if( box[nextH][nextN][nextM] == 0 ){
                    box[nextH][nextN][nextM] = box[location[2]][location[1]][location[0]] + 1;
                    visited[nextH][nextN][nextM] = true;
                    queue.offer( new int[]{ nextM, nextN, nextH });
                }
            }
        }
    }
}

 

반례는 다음과 같다. 

반례:
5 1 7
1 0 0 0 0
0 0 0 -1 0
-1 -1 0 0 0
0 0 1 -1 0
-1 -1 0 0 0
0 0 0 -1 0
1 0 0 0 0

정답: 4
출력: 13

1차 시도 bfs 실행 후 box[h][n][m]:
1 2 3 4 5 
2 3 4 -1 6 
-1 -1 5 6 7 
3 2 1 -1 8 
-1 -1 11 10 9 
14 13 12 -1 10 
1 14 13 12 11

box [0][0][0]에서 1을 발견하면 bfs가 호출되어 주위 이웃들을 탐색해 나간다. 그런데 중요한 점은 1은 하나가 아니다. box [6][0][0]에도 1이 있다. 즉 양방향에서 누적이 일어나야 하는데 1을 처음 발견했을 때 바로 bfs를 호출하니까 다음 1은 찾지 못하고 틀린 값을 출력하는 것이다.

 

그래서 수정한 풀이는 다음과 같다. 일단 큐를 static으로 선언해 주고 main 함수에서 1을 찾았을 때 바로 bfs를 호출하는 것이 아닌, bfs 큐에 해당 좌표를 킵해둔다.

그리고 모든 토마토 위치를 파악했으면, 그때 bfs를 호출해서 큐에 들어있는 토마토들에 대해 이웃 누적을 실행하는 거다.

전체 코드는 아래와 같다.

 

 🔐 2차 시도: 성공

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[][][] box;
    static boolean[][][] visited;
    static int M, N, H;
    static Queue<int[]> queue = new LinkedList<>();
    static int[] dn = { 0, 0, 0, 0, 1, -1 };
    static int[] dm = { 0, 0, 1, -1, 0, 0 };
    static int[] dh = { 1, -1, 0, 0, 0, 0 };

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer line = new StringTokenizer(bf.readLine(), " ");

        M = Integer.parseInt(line.nextToken());
        N = Integer.parseInt(line.nextToken());
        H = Integer.parseInt(line.nextToken());
        box = new int[H][N][M];
        visited = new boolean[H][N][M];

        // [1] 입력 받기
        for( int h = 0; h < H; h++ ){
            for( int n = 0; n < N; n++ ){
                line = new StringTokenizer(bf.readLine(), " ");
                for( int m = 0; m < M; m++ ){
                    int tomato = Integer.parseInt(line.nextToken());
                    box[h][n][m] = tomato;
                }
            }
        }

        // [2] 익은 토마토 찾고 bfs 실행
        for( int h = 0; h < H; h++ ){
            for( int n = 0; n < N; n++ ){
                for( int m = 0; m < M; m++ ){
                    if( box[h][n][m] == 1 && !visited[h][n][m] ){
                        queue.offer( new int[]{ m, n, h } );
                        visited[h][n][m] = true;
                    }
                }
            }
        }

        bfs();

        // [3] max 값 구하기
        int max = 0;
        for( int h = 0; h < H; h++ ){
            for( int n = 0; n < N; n++ ){
                for( int m = 0; m < M; m++ ){
                    if( box[h][n][m] == 0 ) {
                        System.out.println(-1);
                        System.exit(0);
                    }
                    else if( box[h][n][m] > max ){
                        max = box[h][n][m];
                    }
                }
            }
        }
        System.out.println( max - 1 );

    }

    static void bfs(){

        // [2]-2 bfs 실행
        while(!queue.isEmpty()){
            int[] location = queue.poll();

            for( int i = 0; i < 6; i++ ){
                int nextM = location[0] + dm[i];
                int nextN = location[1] + dn[i];
                int nextH = location[2] + dh[i];

                if( nextM < 0 || nextM >= M || nextN < 0 ||
                        nextN >= N || nextH < 0 || nextH >= H ||
                        visited[nextH][nextN][nextM]) continue;

                if( box[nextH][nextN][nextM] == 0 ){
                    box[nextH][nextN][nextM] = box[location[2]][location[1]][location[0]] + 1;
                    visited[nextH][nextN][nextM] = true;
                    queue.offer( new int[]{ nextM, nextN, nextH });
                }
            }
        }
    }
}