백준 24444 JS 풀이

구하는 값

bfs로 접근하는 노드 순서

핵심 아이디어

bfs 기초^^ 주의할점은 인접리스트 오름차순정렬부터 해야함

코드

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

const [n, m, r] = input[0].split(" ").map(Number);
const graph = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i <= m; i++) {
    const [a, b] = input[i].split(" ").map(Number);
    graph[a].push(b);
    graph[b].push(a);
}
graph.forEach((line) => line.sort((a, b) => a - b));
// console.log(graph);
const visited = new Array(n + 1).fill(0);

const queue = [];
queue.push(r);
visited[r] = 1;

let step = 1;
while (queue.length) {
    const cur = queue.shift();

    for (const next of graph[cur]) {
        if (!visited[next]) {
            queue.push(next);
            visited[next] = ++step;
        }
    }
}

console.log(visited.slice(1).join("\n"));

class로 구현이 훨씬 빠름

코드

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

class Que {
    q = [];
    h = 0;
    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, m, r] = input[0].split(" ").map(Number);
const graph = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i <= m; i++) {
    const [a, b] = input[i].split(" ").map(Number);
    graph[a].push(b);
    graph[b].push(a);
}
graph.forEach((line) => line.sort((a, b) => a - b));
// console.log(graph);
const visited = new Array(n + 1).fill(0);

const queue = new Que();
queue.enque(r);
visited[r] = 1;

let step = 1;
while (queue.size()) {
    const cur = queue.deque();

    for (const next of graph[cur]) {
        if (!visited[next]) {
            queue.enque(next);
            visited[next] = ++step;
        }
    }
}

console.log(visited.slice(1).join("\n"));