백준 1389 JS 풀이

구하는 값

케빈 베이컨 단계 합의 최소값

핵심 아이디어

1. 양방향 인접리스트를 만듬
2. 길이 n+1의 visited 배열을 -1로 초기화하고 각 자리에 방문시 몇번째로 방문했는지 기록할거임
3. 1~n까지 각각 bfs를 돌며 visited배열을 만들어주고 배열의 총합 -1을 sumArr에 기록
4. sumArr의 최소값을 가지는 첫번째 idx 출력

코드

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] = 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);
}
// console.log(graph);

const sumArr = [1e9];
function bfs(str, visited) {
    const que = new Que();
    que.enque(str);
    visited[str] = 0;

    while (que.size()) {
        const cur = que.deque();

        for (const next of graph[cur]) {
            if (visited[next] === -1) {
                que.enque(next);
                visited[next] = visited[cur] + 1;
            }
        }
    }
    // console.log("visited", visited);
    return visited.reduce((a, b) => (a += b), 0) + 1;
}

for (let i = 1; i <= n; i++) {
    const visited = new Array(n + 1).fill(-1);
    sumArr.push(bfs(i, visited));
}

// console.log(sumArr);

const min = Math.min(...sumArr);
console.log(sumArr.findIndex((v) => v === min));