🎲 백준 1389번 케빈 베이컨의 6단계 법칙

백준 1389번

💊 처음에 시작점과 끝점을 설정해야한다 생각했더니 복잡해졌는데 시작점만 생각하고 모든 노드를 탐색해면 더 간단히 풀 수 있다.
💊 최단 경로를 구할 때는 BFS를 사용하자.

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

const [N, M] = input.shift().split(" ").map(Number);

const graph = Array.from(new Array(N + 1), () => []);

let result = [0, Infinity];

for (let i = 0; i < M; i++) {
  const [a, b] = input[i].split(" ").map(Number);
  graph[a].push(b);
  graph[b].push(a);
}

const BFS = (start) => {
  let willCheck = [[start, 0]];
  let checked = new Array(N + 1).fill(0);
  let bakon = new Array(N + 1).fill(0);
  checked[start] = 1;
  while (willCheck.length) {
    const [node, count] = willCheck.shift();
    bakon[node] = count;
    for (let i = 0; i < graph[node].length; i++) {
      const next = graph[node][i];
      if (checked[next] === 0) {
        checked[next] = 1;
        let nextCount = count + 1;
        willCheck.push([next, nextCount]);
      }
    }
  }

  return bakon.reduce((a, b) => a + b, 0);
};

for (let i = 1; i <= N; i++) {
  const sum = BFS(i);
  if (result[1] > sum) {
    result = [i, sum];
  }
}

console.log(result[0]);