백준[JS] > 7569번 토마토

문제링크

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

문제풀이

이 문제는 3차원 배열(storage)을 만들고 BFS로 그 3차원 배열의 토마토를 순차적으로 익히면 문제를 풀 수 있다. 여기서 f는 floor, r는 row, c는 column의 약자이다. 처음에는 각 위치에 있는 토마토가 익는데 걸리는 시간을 나타내는 3차원배열을 하나 더 만들어 문제를 풀었는데 시간초과가 났었다. 그래서 3차원 하나의 배열을 가지고 문제를 접근하였는데 또 시간초과가 났었다. 고심끝에 while문 내부 if문의 조건을 storage[nextF] && storage[nextF][nextR] && storage[nextF][nextR][nextC] 형태로 3차원배열의 존재여부를 key값들을 이용해 확인하는 형태에서 43~48 번째 줄 처럼 단순히 숫자를 비교하는 형태로 조건문을 변경하니 시간초과 없이 문제를 풀 수 있었다.

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let [M, N, H] = input
    .shift()
    .split(" ")
    .map((n) => Number(n));

let storage = Array.from({ length: H }, () => {
    return Array.from({ length: N }, () => {
        return 0;
    });
});

for (let f = 0; f < H; ++f) {
    for (let r = 0; r < N; ++r) {
        let line = input[f * N + r].split(" ").map((n) => Number(n));

        storage[f][r] = line;
    }
}

for (let f = 0; f < H; ++f) {
    for (let r = 0; r < N; ++r) {
        for (let c = 0; c < M; ++c) {
            let v = storage[f][r][c];

            if (v === 1) {
                let q = [[f, r, c]];

                while (q.length) {
                    let [nowF, nowR, nowC] = q.shift();

                    // 윗박스,아랫박스스, 상,하,좌,우
                    let df = [1, -1, 0, 0, 0, 0],
                        dr = [0, 0, 1, -1, 0, 0],
                        dc = [0, 0, 0, 0, -1, 1];

                    for (let step = 0; step < 6; ++step) {
                        let [nextF, nextR, nextC] = [nowF + df[step], nowR + dr[step], nowC + dc[step]];

                        if (
                            nextF >= 0 &&
                            nextF < H &&
                            nextR >= 0 &&
                            nextR < N &&
                            nextC >= 0 &&
                            nextC < M &&
                            storage[nextF][nextR][nextC] !== -1 &&
                            (storage[nextF][nextR][nextC] === 0 || storage[nextF][nextR][nextC] > storage[nowF][nowR][nowC] + 1)
                        ) {
                            storage[nextF][nextR][nextC] = storage[nowF][nowR][nowC] + 1;
                            q.push([nextF, nextR, nextC]);
                        }
                    }
                }
            }
        }
    }
}

let answer = 0;
for (let f = 0; f < H; ++f) {
    for (let r = 0; r < N; ++r) {
        for (let c = 0; c < M; ++c) {
            if (storage[f][r][c] === 0) {
                answer = -1;
                console.log(answer);
                return;
            } else if (storage[f][r][c] >= 1) {
                answer = Math.max(answer, storage[f][r][c] - 1);
            }
        }
    }
}

console.log(answer);