[문제 풀이] 백준 7569번 토마토 JAVA

문제

  문제접근 방법   

해당 문제는 토마토 농장에서 익은 토마토는 1, 안익으면 0, 비어있는 상자는 -1이라하고 익은 토마토 상하좌우위아래는  하루가 지나면 익는다고 할때 얼마의 시간이 지나야 토마토가 다익는지를구하는 프로그램을 작성하는 문제이다.

문제를 일고 DFS는 동시성 보장이 어려워 최소 날짜 계산에 부적합하다고 판단해 BFS를 통해 문제를 풀이하였다.

3차원 배열을 통해 BFS를 접근하는 것은 처음이어서 어렵다고 느끼었지만 실제로는 그렇게 어렵지 않았다.

코드는 아래와 같다.

< 최종 코드 >

import java.util.*;

public class Main {
    public static boolean[][][] visited;
    public static int day = 0;

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        Queue<int[]> queue = new LinkedList<>();

        int m = s.nextInt();
        int n = s.nextInt();
        int h = s.nextInt();

        int[][][] box = new int[h][n][m];
        visited = new boolean[h][n][m];

        for (int k = 0; k < h; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    box[k][i][j] = s.nextInt();
                    if (box[k][i][j] == 1) {
                        queue.offer(new int[]{k, i, j, 0}); 
                        visited[k][i][j] = true;
                    }
                }
            }
        }

        bfs(queue, box);

        for (int k = 0; k < h; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (box[k][i][j] == 0) {
                        System.out.println(-1);
                        return;
                    }
                }
            }
        }

        System.out.println(day);
    }

    public static void bfs(Queue<int[]> q, int[][][] box) {
        int[] dx = {1, -1, 0, 0, 0, 0};
        int[] dy = {0, 0, 1, -1, 0, 0};
        int[] dz = {0, 0, 0, 0, 1, -1};

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int z = cur[0];
            int y = cur[1];
            int x = cur[2];
            int d = cur[3];
            day = Math.max(day, d);

            for (int i = 0; i < 6; i++) {
                int nz = z + dz[i];
                int ny = y + dy[i];
                int nx = x + dx[i];

                if (nz >= 0 && nz < box.length &&
                    ny >= 0 && ny < box[0].length &&
                    nx >= 0 && nx < box[0][0].length) {

                    if (box[nz][ny][nx] == 0 && !visited[nz][ny][nx]) {
                        box[nz][ny][nx] = 1;
                        visited[nz][ny][nx] = true;
                        q.offer(new int[]{nz, ny, nx, d + 1});
                    }
                }
            }
        }
    }
}

여기서 핵심은 3차원 배열로 선언하는 것이아니라 토마토 상태를 입력받을때 익은 값들을 queue.offer(new int[]{k, i, j, 0}); 이롸 같이 모두 저장하여 bfs에 넘겨버리는 것으로 동시성을 확보하는부분이라고 생각된다.

만약 이렇게 작성하지 않는다면 동시에 토마토가 익는것을 체크하는 것도 어렵지만 일수를 동기화하고 갱신하는 것이 굉장히 복잡하고 어려울 것으로 예상된다. 

 

  마무리  

사실 3차원으로 접근해야하고 코드가 길어 어렵게 느껴지지만 동시성이라는 부분만 해결한다면 구현자체 난이도는 높지 않다고 생각한다. 하지만 첫 3차원 접근문제이므로 미리 경험해보고 정리하는 것이 좋다고 생각된다. 

  추가 코드 분석 및 풀이  

위에서 언급하였듯이 DFS 한 곳을 끝까지 탐색한 후 다른 곳을 탐색하기 때문에 동시성을 확보하는 부분이 어려워 부적합하다.