백준 7569 JS 풀이

구하는 값

3차원 창고에서 토마토가 다 익는데 걸리는 시간

핵심 아이디어

que안에 익은 토마토를 넣어놓고 상하좌우위아래로 bfs를 돌림

코드1

const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n')

class Que {
    q = [];
    h = 0;
    t = 0;
    push(v) {
        this.q[this.t++] = v;
    }
    shift() {
        const v = this.q[this.h];
        delete this.q[this.h++];
        return v;
    }
    length() {
        return this.t - this.h;
    }
}

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

const graph = Array.from({ length: h }, () => Array.from({ length: n }, () => []));
// console.log(graph);

const que = new Que();
let k = h;
while (k--) {
    for (let i = 0; i < n; i++) {
        const line = input[k * n + i + 1].split(" ").map(Number);
        line.forEach((v, j) => {
            if (v === 1) que.push([k, i, j, 1]);
        });
        graph[k][i].push(...line);
    }
}

// console.log(graph); // z,y,x
// console.log(que);

const dx = [-1, 1, 0, 0, 0, 0],
    dy = [0, 0, -1, 1, 0, 0],
    dz = [0, 0, 0, 0, -1, 1];

let max = 0;
const bfs = () => {
    while (que.length()) {
        const [z, y, x, d] = que.shift();

        max = Math.max(d, max);

        for (let i = 0; i < 6; i++) {
            const nx = x + dx[i],
                ny = y + dy[i],
                nz = z + dz[i];

            if (nx < 0 || nx >= m || ny < 0 || ny >= n || nz < 0 || nz >= h) continue;
            // console.log("nz,ny,nx", nz, ny, nx);
            if (!graph[nz][ny][nx]) {
                graph[nz][ny][nx] = d;
                que.push([nz, ny, nx, d + 1]);
            }
        }
    }
};

bfs();
// console.log(graph);

outer: for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
        for (let z = 0; z < h; z++) {
            if (!graph[z][i][j]) {
                max = 0;
                break outer;
            }
        }
    }
}

console.log(max - 1);

코드2

const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n')

class Que {
    q = [];
    h = 0;
    t = 0;
    push(v) {
        this.q[this.t++] = v;
    }
    shift() {
        const v = this.q[this.h];
        delete this.q[this.h++];
        return v;
    }
    length() {
        return this.t - this.h;
    }
}

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

const graph = Array.from({ length: h }, () => Array.from({ length: n }, () => []));
// console.log(graph);

const que = new Que();
let k = h;
let total = m * n * h;
while (k--) {
    for (let i = 0; i < n; i++) {
        const line = input[k * n + i + 1].split(" ").map(Number);
        line.forEach((v, j) => {
            if (v === 1) {
                que.push([k, i, j, 1]);
                total--;
            }
            if (v === -1) total--;
        });
        graph[k][i].push(...line);
    }
}

// console.log(graph); // z,y,x
// console.log(que);

const dx = [-1, 1, 0, 0, 0, 0],
    dy = [0, 0, -1, 1, 0, 0],
    dz = [0, 0, 0, 0, -1, 1];

let max = 0;
const bfs = () => {
    while (que.length()) {
        const [z, y, x, d] = que.shift();

        max = Math.max(d, max);

        for (let i = 0; i < 6; i++) {
            const nx = x + dx[i],
                ny = y + dy[i],
                nz = z + dz[i];

            if (nx < 0 || nx >= m || ny < 0 || ny >= n || nz < 0 || nz >= h) continue;
            // console.log("nz,ny,nx", nz, ny, nx);
            if (!graph[nz][ny][nx]) {
                total--;
                graph[nz][ny][nx] = d;
                que.push([nz, ny, nx, d + 1]);
            }
        }
    }
};

bfs();

console.log(total ? -1 : max - 1);

3차원을 다루는 방법을 처음해봤다. 시험때만나면 당황했을듯..

그리고 처음방법으로 삼중for문은 너무 역해서 다른 방법을 찾다 graph만들때 순회를하니깐 그때 전체개수에서 1, -1의 개수를빼주고 bfs를 돌며 -1씩해주면 전체개수가 0이 아니라면 안익은 토마토가 남아있다는 뜻이므로 삼중for문 없이 판단할 수 있다.