[JS] 백준 7569번 토마토

---

문제 링크

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

풀이 전략

하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다.
철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다. 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다.
둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다.
각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다.
정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

코드 

const fs = require("fs");
const [init, ...input] = fs
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n");

// queue 구현.
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class Queue {
    constructor() {
        this.head = null;
        this.rear = null;
        this.length = 0;
    }

    enqueue(data) {
        const node = new Node(data);
        if (!this.head) {
            this.head = node;
        } else {
            this.rear.next = node;
        }
        this.rear = node;
        this.length++;
    }

    dequeue() {
        if (!this.head) {
            return false;
        }
        const data = this.head.data;
        this.head = this.head.next;
        this.length--;

        return data;
    }
}
//

const [m, n, h] = init.split(" ").map(Number);

solution(input);

function solution(arr) {
    const queue = new Queue();
    const box = Array.from({ length: h }, () =>
        Array.from({ length: n }, () => Array.from({ length: m }).fill(0))
    );

    for (let i = 0; i < h; i++) {
        for (let j = 0; j < n; j++) {
            box[i][j] = arr.shift().split(" ").map(Number);
        }
    }

    for (let i = 0; i < h; i++) {
        for (let j = 0; j < n; j++) {
            for (let k = 0; k < m; k++) {
                if (box[i][j][k] === 1) {
                    queue.enqueue([i, j, k, 0]);
                }
            }
        }
    }

    console.log(bfs(box, queue));
}

function bfs(box, queue) {
    const dh = [0, 0, 1, -1, 0, 0];
    const dn = [0, 0, 0, 0, -1, 1];
    const dm = [1, -1, 0, 0, 0, 0];

    let answer = 0;

    while (queue.length) {
        const [qh, qn, qm, day] = queue.dequeue();
        answer = day;
        for (let i = 0; i < 6; i++) {
            const [nh, nn, nm] = [qh + dh[i], qn + dn[i], qm + dm[i]];

            if (range_check(nh, nn, nm) && box[nh][nn][nm] === 0) {
                box[nh][nn][nm] = 1;
                queue.enqueue([nh, nn, nm, day + 1]);
            }
        }
    }

    for (let i = 0; i < h; i++) {
        for (let j = 0; j < n; j++) {
            for (let k = 0; k < m; k++) {
                if (box[i][j][k] === 0) {
                    return -1;
                }
            }
        }
    }

    return answer;
}

function range_check(nh, nn, nm) {
    if (0 <= nh && nh < h && 0 <= nn && nn < n && 0 <= nm && nm <= m)
        return true;
    else return false;
}

 

회고

이전 토마토문제에서 z축이 추가되었다. 코드도 그에 맞게 인풋처리를 해주었고 기존에 2차원에서 작성하였던 코드에서도 z축만 추가해 주었다. 삼차원 배열을 사용한다는 것만 빼면 이전 토마토 문제와 다른게 없었다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)