[백준 2644] 촌수계산 with node.js

📌 문제링크

https://www.acmicpc.net/problem/2644

📌 풀이

• 촌수를 구해야하는 targetA에서 시작해서 targetB까지의 길이(distance)를 구한다
• BFS를 돌면서 방문체크를 하고 degree값을 1씩 증가시키면서 targetB에 도달하였을 때의 값을 구함

📌 코드

const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString().trim()
    : `9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const getDegreeOfKinshipByBFS = (startVertex) => {
  const visited = new Array(N + 1).fill(false);
  const queue = [[startVertex, 0]];

  while (queue.length) {
    const [vertex, degree] = queue.shift();

    if (vertex === targetVertexB) return degree;

    for (let nextVertex of familyTree[vertex]) {
      if (visited[nextVertex]) continue;
      visited[nextVertex] = true;

      queue.push([nextVertex, degree + 1]);
    }
  }

  return -1;
};

const N = parseInt(input());
const [targetVertexA, targetVertexB] = input().split(' ').map(Number);
const numOfRelationship = parseInt(input());
const familyTree = Array.from(new Array(N + 1), () => new Array());

for (let i = 0; i < numOfRelationship; i++) {
  const [vertexA, vertexB] = input().split(' ').map(Number);

  familyTree[vertexA].push(vertexB);
  familyTree[vertexB].push(vertexA);
}

console.log(getDegreeOfKinshipByBFS(targetVertexA));