[백준 - 7569] 토마토 - Java

문제 설명

 

7569번: 토마토

 

풀이 회고

해당 문제는 BFS를 이용하여 풀이할 수 있었는데, 익은 토마토를 기점으로 익지 않은 토마토들이 점차 확산되어가며 익어간다는 점 그리고 익는데 며칠이 걸리는지를 구해야 한다는 점에서 BFS를 떠올릴 수 있었습니다.

이때 DFS를 사용하지 않았던 이유는 익은 토마토들이 여러 개 있을 때 익은 토마토들을 기점으로 동시 다발적으로 익지 않은 토마토들로 확산되어 갈텐데 DFS는 우선적으로 하나의 익은 토마토를 기점으로 확산시키기 때문에 이 문제 풀이에 적합하지 않다고 생각했습니다.

문제에 따르면 토마토가 익어가는 방향은 x, y, z 축 각각의 방향으로 총 6가지로 정의됩니다. 이를 위해 각각의 dx, dy, dz 1차원 배열을 정의해 줍니다. 아울러, x, y, z 축에 대한 토마토의 위치를 저장하기 위해 3차원의 byte형 배열을 활용했습니다. (byte로 정의한 이유는 배열 요소의 값이 -1, 0, 1 중 하나이기 때문입니다.)

 

    static byte[][][] board;
    static int[] dx = {1, -1, 0, 0, 0, 0}, dy = {0, 0, 1, -1, 0, 0}, dz = {0, 0, 0, 0, 1, -1};

이후 토마토 창고 값들을 입력받을 때 익은 토마토들에 대해 방문처리를 해준 후 별도의 해당 좌표(x, y, z)에 대한 값과 걸린 일수(days) 정보를 일차원 배열에 저장하여 Queue에 모두 넣어주었고, 익지 않은 토마토의 경우 별도로 카운팅하여 0일 경우 소요되는 일수도 0이므로 그대로 결과값으로 0을 출력시키고 종료하도록 했습니다.

 

        boolean[][][] visited = new boolean[h][n][m];
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < n; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < m; k++) {
                    byte tomato = Byte.parseByte(st.nextToken());
                    board[i][j][k] = tomato;
                    if (tomato == 1) {
                        queue.add(new int[]{j, k, i, 0});
                        visited[i][j][k] = true;
                    } else if (tomato == 0) {
                        noRipeTomato++;
                    }
                }
            }
        }
        
        if (noRipeTomato == 0) {
            System.out.println(0);
            return;
        }

 

그리고 이를 기점으로 BFS 탐색을 통해 앞서 정의한 6가지 방향으로 확산되도록 합니다. 이때 익지 않은 토마토를 발견할 때마다 방문 처리 하고 일수(day)를 1씩 증가시키며 현재 걸린 일수를 갱신해줍니다. 아울러 익었는지 안 익었는지를 추후에 분간하기 위해 익은 토마토의 값 1을 할당해주고 앞서 익지 않은 토마토의 개수(noRipeTomato)의 값을 감소시켜줍니다.

 

    private static void spread(boolean[][][] visited, Queue<int[]> queue) {
        int nx, ny, nz;

        while (!queue.isEmpty()) {

            int[] positions = queue.poll();

            for (int i = 0; i < 6; i++) {
                nx = positions[0] + dx[i];
                ny = positions[1] + dy[i];
                nz = positions[2] + dz[i];

                if (nx < 0 || nx > n - 1 || ny < 0 || ny > m - 1 || nz < 0 || nz > h - 1 ||
                    board[nz][nx][ny] != 0 || visited[nz][nx][ny]) {
                    continue;
                }

                board[nz][nx][ny] = 1;
                visited[nz][nx][ny] = true;
                noRipeTomato--;
                days = Math.max(days, positions[3] + 1);
                queue.add(new int[]{nx, ny, nz, positions[3] + 1});
            }
        }
    }

최종적으로 익지 않은 토마토가 존재하는 경우(noRipeTomato != 0)에는 -1을 출력시켜주었고, 익지 않은 토마토가 존재하지 않는 경우에는 너비 우선 탐색을 진행하면서 갱신해주었던 걸린 일수(days)를 출력시켜주도록 합니다.

 

        if (noRipeTomato != 0) {
            System.out.println(-1);
            return;
        }

        System.out.println(days);

 

 

전체 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

    static byte[][][] board;
    static int[] dx = {1, -1, 0, 0, 0, 0}, dy = {0, 0, 1, -1, 0, 0}, dz = {0, 0, 0, 0, 1, -1};
    static int m, n, h, days = 0, noRipeTomato = 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());

        board = new byte[h][n][m];

        boolean[][][] visited = new boolean[h][n][m];
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < n; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < m; k++) {
                    byte tomato = Byte.parseByte(st.nextToken());
                    board[i][j][k] = tomato;
                    if (tomato == 1) {
                        queue.add(new int[]{j, k, i, 0});
                        visited[i][j][k] = true;
                    } else if (tomato == 0) {
                        noRipeTomato++;
                    }
                }
            }
        }

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

        spread(visited, queue);

        if (noRipeTomato != 0) {
            System.out.println(-1);
            return;
        }

        System.out.println(days);
    }

    private static void spread(boolean[][][] visited, Queue<int[]> queue) {
        int nx, ny, nz;

        while (!queue.isEmpty()) {

            int[] positions = queue.poll();

            for (int i = 0; i < 6; i++) {
                nx = positions[0] + dx[i];
                ny = positions[1] + dy[i];
                nz = positions[2] + dz[i];

                if (nx < 0 || nx > n - 1 || ny < 0 || ny > m - 1 || nz < 0 || nz > h - 1 ||
                    board[nz][nx][ny] != 0 || visited[nz][nx][ny]) {
                    continue;
                }

                board[nz][nx][ny] = 1;
                visited[nz][nx][ny] = true;
                noRipeTomato--;
                days = Math.max(days, positions[3] + 1);
                queue.add(new int[]{nx, ny, nz, positions[3] + 1});
            }
        }
    }
}

 

 

참고자료

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