[백준] 2644번 : 촌수계산 (실버Ⅱ) by node.js

▷ 문제 :2644번 : 촌수계산

2644번: 촌수계산

▷ 해결 날짜 : 2022.06.30
▷ 소요 시간 : 1시간 30분
▷ 풀이 과정 :

DFS / BFS 관련 문제로 쉽게 접근하면 시작점부터 끝점까지의 거리가 얼마인지 반환하는 문제이다.

단, 여기서 촌수계산이 들어가면서 문제가 복잡해진다.

 

주어진 문제가 짧으므로 아래를 읽어보도록 하자.

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

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

이러한 문제가 주어졌는데, 오랜만에 풀기도 하고 너무 혼란스러워서 감을 못 잡다가 실제 촌수까지 찾아보면서 생각해보니 그냥 쉽게 시작점을 기준으로 하나씩 늘려가면 쉽게 풀 수 있는 문제였다.

 

나(0촌)를 기준으로 부모(1촌)와 자식(1촌)이 존재할 수 있고, 나의 형제자매들(2촌), 할아버지(2촌), 할머니(2촌) 부모의 형제자매들(3촌),... 이런 식으로 촌수가 잡혀있다 보니 결국 촌수를 따지는 건 부모가 기준이며 구현을 할 때는 이러한 특징을 알아두고 나를 기준으로 1촌씩 늘려가면 되는 것이었다.

 

(나도 적다 보니 무슨 말인지 잘 모르겠다. 그냥 코드 보고 대충 이해하고 넘어가자)

 

▷ 구현

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

const n = Number(input[0]);
const [p, q] = input[1].split(" ").map(Number);
const m = Number(input[2]);
const grph = [...Array(n + 1)].map((e) => []);

for (let i = 3; i < m + 3; i++) {
  let [parent, child] = input[i].split(" ").map(Number);
  grph[parent].push(child);
  grph[child].push(parent);
}

const bfs = (graph, startNode, targetNode) => {
  const visited = [];
  let needVisit = [[startNode, 0]];

  while (needVisit.length !== 0) {
    const [node, cnt] = needVisit.shift();
    if (node === targetNode) return cnt;
    if (!visited.includes(node)) {
      visited.push(node);
      let nodes = graph[node].map((e) => [e, cnt + 1]);
      needVisit = [...needVisit, ...nodes];
    }
  }

  return -1;
};

console.log(bfs(grph, p, q));

 

▷ 복기 :

다른 사람 코드를 보질 못해서 잘 모르겠으나 굳이 비교할 필요성을 느끼지는 못했다.

좀 더 익숙해지게 이 정도 난이도에서 풀어봐야겠다.