[Java | Algorithm] 백준 7569 - 토마토

출처 - https://www.acmicpc.net/problem/7569

1) 문제 설명

2) 접근 방식

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

예전에 위 링크에 있는 문제를 푼 기억이 있어서

bfs로 풀면 되겠다라고 생각했고

방향이 추가된 총 6방향 3차원 배열을 활용해서 풀어야겠다고 생각했습니다.

3) 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, M, H;
    static int[][][] map;
    static Queue<Node> q = new ArrayDeque<>();
    static int[] dy = {-1, 1, 0, 0, 0, 0};
    static int[] dx = {0, 0, -1, 1, 0, 0};
    static int[] dz = {0, 0, 0, 0, -1, 1};

    static class Node {
        int z, y, x;

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

    public static void main(String[] args) throws Exception {
        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());

        map = new int[H][N][M];

        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++) {
                    map[h][n][m] = Integer.parseInt(st.nextToken());
                    if (map[h][n][m] == 1) {
                        q.offer(new Node(h, n, m)); // 익은 토마토 위치 큐에 저장
                    }
                }
            }
        }

        int result = bfs();
        System.out.println(result);
    }

    static int bfs() {
        int maxDays = 0;

        while (!q.isEmpty()) {
            Node node = q.poll();
            for (int d = 0; d < 6; d++) { // 6방향 탐색
                int nz = node.z + dz[d];
                int ny = node.y + dy[d];
                int nx = node.x + dx[d];

                if (nz < 0 || ny < 0 || nx < 0 || nz >= H || ny >= N || nx >= M) continue;
                if (map[nz][ny][nx] == 0) { // 익지 않은 토마토
                    map[nz][ny][nx] = map[node.z][node.y][node.x] + 1;
                    q.offer(new Node(nz, ny, nx));
                }
            }
        }

        // 모든 토마토가 익었는지 확인하고 최대 일수 계산
        for (int h = 0; h < H; h++) {
            for (int n = 0; n < N; n++) {
                for (int m = 0; m < M; m++) {
                    if (map[h][n][m] == 0) {
                        return -1; // 익지 않은 토마토가 남아있는 경우
                    }
                    maxDays = Math.max(maxDays, map[h][n][m]);
                }
            }
        }

        // 시작이 1로 표시되었으므로 일수는 (최대값 - 1)
        return maxDays == 1 ? 0 : maxDays - 1;
    }
}

2차원 배열과 차이점은

static int N, M, H;
static int[][][] map;
static Queue<Node> q = new ArrayDeque<>();
static int[] dy = {-1, 1, 0, 0, 0, 0};
static int[] dx = {0, 0, -1, 1, 0, 0};
static int[] dz = {0, 0, 0, 0, -1, 1};

static class Node {
    int z, y, x;

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

이렇게 선언해줘서 4방향 탐색하던 기존 코드에서 6방향으로 2번의 탐색이 추가됐다고 생각하면 됩니다.

 

중요한 bfs 코드를 보면

while (!q.isEmpty()) {
    Node node = q.poll();
    for (int d = 0; d < 6; d++) { // 6방향 탐색
        int nz = node.z + dz[d];
        int ny = node.y + dy[d];
        int nx = node.x + dx[d];

        if (nz < 0 || ny < 0 || nx < 0 || nz >= H || ny >= N || nx >= M) continue;
        if (map[nz][ny][nx] == 0) { // 익지 않은 토마토
            map[nz][ny][nx] = map[node.z][node.y][node.x] + 1;
            q.offer(new Node(nz, ny, nx));
        }
    }
}

6방향을 탐색하면서 배열 범위가 벗어나지 않고 토마토가 익지 않았다면

익지 않은 토마토 좌표의 값을 큐에 넣어줍니다.

그 전의 토마토 값의 +1을 더하여 날짜를 계산합니다.

// 모든 토마토가 익었는지 확인하고 최대 일수 계산
for (int h = 0; h < H; h++) {
    for (int n = 0; n < N; n++) {
        for (int m = 0; m < M; m++) {
            if (map[h][n][m] == 0) {
                return -1; // 익지 않은 토마토가 남아있는 경우
            }
            maxDays = Math.max(maxDays, map[h][n][m]);
        }
    }
}

마지막으로 모든 토마토가 익었는 지 확인해줍니다

만약에 하나라도 익지 않은 토마토가 남아있는데 경우 -1 return

익은 토마토 값 중에서 가장 큰 값으로 날짜(maxDays)를 갱신해줍니다.

정리

예전에 풀었던 2차원 배열 문제를 이번에는 3차원 배열로 확장해 푸는 문제였기에 상대적으로 어렵지 않게 해결할 수 있었습니다. 역시 알고리즘 문제는 꾸준히 많은 문제를 풀어보는 것이 중요하다는 걸 다시 한번 느꼈습니다.

많이 풀어보자...