백준 18405 JS 풀이

구하는 값

바이러스의 종류

핵심 아이디어

상하좌우로 바이러스가 퍼지고 더 작은 숫자 바이러스가 기록되므로

큐에 작은 바이러스 순서대로 넣는다면 작은 바이러스가 기록될 것이고 기록된 곳에는 방문을 하지 않는 방식으로 bfs를 돌리면 해결됨

코드

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

class Queue {
    constructor() {
        this.q = [];
        this.h = 0;
        this.t = 0;
    }
    enque(v) {
        this.q[this.t++] = v;
    }
    deque() {
        const v = this.q[this.h];
        delete this.q[this.h++];
        return v;
    }
    size() {
        return this.t - this.h;
    }
}

const [n, k] = input[0].split(" ").map(Number);
const graph = [];
let viruse = [];
for (let i = 1; i <= n; i++) {
    const line = input[i].split(" ").map(Number);
    line.forEach((v, j) => {
        if (v !== 0) viruse.push([v, i - 1, j]);
    });
    graph.push(line);
}
// console.log(graph);

viruse.sort((a, b) => a[0] - b[0]);
// console.log(viruse);

const [s, x, y] = input[n + 1].split(" ").map(Number);

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

const queue = new Queue();

function bfs(dep) {
    for (const [cv, cy, cx] of viruse) {
        queue.enque([cv, cy, cx, dep]);
        graph[cy][cx] = cv;
    }

    while (queue.size()) {
        const [cv, cy, cx, dep] = queue.deque();

        if (dep === s) return;

        for (let i = 0; i < 4; i++) {
            const ny = cy + dy[i],
                nx = cx + dx[i];

            if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;

            if (!graph[ny][nx]) {
                queue.enque([cv, ny, nx, dep + 1]);
                graph[ny][nx] = cv;
            }
        }
    }
}

bfs(0);
// console.log(graph);
console.log(graph[x - 1][y - 1]);