[BOJ] 토마토 - 7569

🎨 문제

7569번: 토마토

📘 풀이

이 문제는 BFS로 풀 수 있습니다. 이전에 풀이한 문제와 유사하여 이 글을 읽고 오시면 도움이 될 것입니다. 차이점은 토마토 농장이 높이(H)가 생긴 겁입니다.

 

문제 풀이 과정을 정리하면 다음과 같습니다.

 

1. 익어야할 남은 토마토의 개수를 계산
2. BFS를 통해 익은 토마토와 인접한 토마토를 익힘
3. BFS가 종료되었을 때 남은 토마토가 모두 익었다면 -1, 아니라면 토마토가 익기까지 걸린 시간 반환

농장에 높이(H)가 생겼으므로 농장의 상태를 저장하는 배열은 3차원 배열이 됩니다.

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

 

입력을 받을 때 익은 토마토를 리스트에 저장하고 벽의 개수를 세줍니다.

if (FARM[i][j][k] == 1) {
    VISITED[i][j][k] = true;
    TOMATOS.add(new int[]{i, j, k, 0});
}
if (FARM[i][j][k] == -1) {
    VISITED[i][j][k] = true;
    WALL += 1;
}

그 후 익어야할 남은 토마토는 다음과 같이 계산할 수 있습니다.

int rest = N * M * H - WALL - TOMATOS.size();

BFS를 진행할 때 높이(H)가 생겼으므로 6가지 방향으로 탐색이 가능합니다.

final int[] dI = {0, 0, 0, 0, 1, -1};
final int[] dJ = {0, 0, 1, -1, 0, 0};
final int[] dK = {1, -1, 0, 0, 0, 0};

그 후 BFS를 진행합니다. 여기서 이전 풀이와 다른 점은 count를 계산하기 위해 queue의 길이만큼 반복하여 한 레벨 탐색을 하는 것이 아닌 queue에 삽입된 노드 자체에 count 값을 저장하여 탐색이 진행될 때마다 해당 값은 1씩 증가시키는 방법을 사용했습니다.

while (!TOMATOS.isEmpty()) {
    int[] cur = TOMATOS.poll();
    int curI = cur[0];
    int curJ = cur[1];
    int curK = cur[2];

    for (int i = 0; i < 6; i++) {
        int nI = curI + dI[i];
        int nJ = curJ + dJ[i];
        int nK = curK + dK[i];

        if (nI < 0 || nJ < 0 || nK < 0 || nI >= H || nJ >= N || nK >= M) {
            continue;
        }

        if (VISITED[nI][nJ][nK]) {
            continue;
        }

        VISITED[nI][nJ][nK] = true;
        TOMATOS.add(new int[]{nI, nJ, nK, cur[3] + 1});
        rest -= 1;
        count = cur[3] + 1;
    }
}

 

📗 코드

 

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

import static java.lang.System.in;

public class Main {

    static int N, M, H, WALL;
    static int[][][] FARM;
    static boolean[][][] VISITED;
    static Queue<int[]> TOMATOS = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        int[] input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        M = input[0];
        N = input[1];
        H = input[2];
        WALL = 0;
        FARM = new int[H][N][M];
        VISITED = new boolean[H][N][M];

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N; j++) {
                FARM[i][j] = Arrays.stream(br.readLine().split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray();
                for (int k = 0; k < M; k++) {
                    if (FARM[i][j][k] == 1) {
                        VISITED[i][j][k] = true;
                        TOMATOS.add(new int[]{i, j, k, 0});
                    }
                    if (FARM[i][j][k] == -1) {
                        VISITED[i][j][k] = true;
                        WALL += 1;
                    }
                }
            }
        }

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

    private static int bfs() {
        final int[] dI = {0, 0, 0, 0, 1, -1};
        final int[] dJ = {0, 0, 1, -1, 0, 0};
        final int[] dK = {1, -1, 0, 0, 0, 0};

        int rest = N * M * H - WALL - TOMATOS.size();

        if (rest == 0) return 0;

        int count = 0;

        while (!TOMATOS.isEmpty()) {
            int[] cur = TOMATOS.poll();
            int curI = cur[0];
            int curJ = cur[1];
            int curK = cur[2];

            for (int i = 0; i < 6; i++) {
                int nI = curI + dI[i];
                int nJ = curJ + dJ[i];
                int nK = curK + dK[i];

                if (nI < 0 || nJ < 0 || nK < 0 || nI >= H || nJ >= N || nK >= M) {
                    continue;
                }

                if (VISITED[nI][nJ][nK]) {
                    continue;
                }

                VISITED[nI][nJ][nK] = true;
                TOMATOS.add(new int[]{nI, nJ, nK, cur[3] + 1});
                rest -= 1;
                count = cur[3] + 1;
            }
        }

        return rest == 0 ? count : -1;
    }
}