[boj] 1389. 케빈 베이컨의 6단계 법칙 (node.js)

문제 요약

[boj] 1389. 케빈 베이컨의 6단계 법칙 (node.js)

풀이

• BFS로 각각의 거리를 계산하고 저장해준 후 최소 거리를 가지는 사람의 인덱스를 출력
• '최단 거리' 문제는 BFS를 활용해야 동일 depth의 노드가 같은 거리를 가지도록 할 수 있음을 잊지 말자!
• results[init][elem] = results[init][node] + 1; 를 통해서 거리를 갱신했다.

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let cnt = 0;
const input = () => stdin[cnt++].split(" ").map(Number);

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  const [N, M] = input();
  let graph = [];
  let visited = [];
  let results = [];
  let sum = [];
  for (let i = 1; i <= N; i++) {
    results[i] = new Array(N + 1).fill(0);
  }
  for (let i = 0; i < M; i++) {
    const arr = input();
    if (!graph[arr[0]]) graph[arr[0]] = [];
    if (!graph[arr[1]]) graph[arr[1]] = [];
    graph[arr[0]].push(arr[1]);
    graph[arr[1]].push(arr[0]);
  }
  for (let i = 1; i <= N; i++) {
    visited = [];
    bfs(i, i);
    sum[i - 1] = results[i].reduce((sum, elem) => sum + elem, 0);
  }
  console.log(sum.indexOf(Math.min(...sum)) + 1);
  process.exit();
  function bfs(init, val) {
    let queue = [val];
    while (queue.length) {
      let node = queue.shift();
      visited[node] = 1;
      graph[node].forEach((elem) => {
        if (!visited[elem]) {
          visited[elem] = 1;
          results[init][elem] = results[init][node] + 1;
          queue.push(elem);
        }
      });
    }
  }
});