[Javascript] 백준 2644: 촌수계산

문제
우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

입력
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

출력
입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

정답코드

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

const totalPeople = +input[0];
const [startPerson, endPerson] = input[1].split(" ").map(Number);
const totalRelations = +input[2];
const relations = input.slice(3).map((line) => line.split(" ").map(Number));

const adjacencyList = Array.from({ length: totalPeople + 1 }, () => []);
const visited = Array.from({ length: totalPeople + 1 }, () => false);

if (totalPeople === 1) return console.log(-1);

for (let i = 0; i < totalRelations; i++) {
  let [personX, personY] = relations[i];
  adjacencyList[personX].push(personY);
  adjacencyList[personY].push(personX);
}

const bfs = (startPerson) => {
  const queue = [[startPerson, 0]];

  while (queue.length) {
    const [currentPerson, distance] = queue.shift();
    const neighbors = adjacencyList[currentPerson];

    if (visited[currentPerson]) continue;
    if (currentPerson === endPerson) return distance;

    visited[currentPerson] = true;

    for (let i = 0; i < neighbors.length; i++) {
      let neighbor = neighbors[i];
      if (visited[neighbor]) continue;
      if (neighbor === endPerson) return distance + 1;

      queue.push([neighbor, distance + 1]);
    }
  }

  return -1;
};

console.log(bfs(startPerson));

촌수를 계산하는 문제이다. 즉 경로를 계산하는 문제라고 생각할 수 있고 일반적으로 bfs를 최단 경로를 구할 때 사용하기도 하고 떠올리면 될 것 같다. 우선 주어진 예제 입력 데이터를 totalPeople(전체 사람 수), [startPerson, endPerson](촌수를 계산해야 하는 서로 다른 두 사람), totalRelations(관계의 수), relations(관계도)로 입력받았다. 그다음 서로 관계있는 직접 연결되는 1촌 사이의 관계를 그래프 형태로 저장하기 위해 adjacencyList에 입력받았다. visited 배열은 촌수 사이의 관계를 확인을 했으면 똑같은 촌수를 다시 방문했을 경우를 막아주기 위해 사용하였다.

이제 나머지 bfs함수는 startPerson를 주었을때 시작점을 큐에 사람 번호와, 촌수 거리를 계산할 값인 0을 같이 넣어주었다. 그 다음 큐를 다 순회할때까지 while을 돌면서 처음 주어진 번호에 해당하는 currentPerson(처음은 7)과 distance(0)이 주어지고 해당하는 1촌 사이의 관계 그래프를 neighbors 변수에 담는다. 그 다음 방문 여부와 찾아야 할 대상 endPerson과 일치하는지 확인한다. 둘 다 조건을 만족하지 않는다면 neighbors변수에 할당된 배열 adjacencyList[7] 길이만큼 반복문을 순회하면서 안에 값들이 방문을 했었는지, endPerson인지 확인 후 아니라면 queue에 해당하는 번호와 거리를 1증가 시켜 푸쉬 반복해 주면 된다.

• if (totalPeople === 1) return console.log(-1); 사람이 1명일 경우
• bfs에서도 아무 값이 리턴되지 않으면 없는 관계기 때문에 -1을 리턴