[백준 2644 - Node.js] 촌수계산

🔗 문제 링크

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

2644번: 촌수계산

✏️ 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const n = +input.shift();
const [person1, person2] = input.shift().split(' ');
const m = +input.shift();
const relations = input.reduce((acc, v) => {
  const [parent, child] = v.split(' ');
  if (!acc[parent]) {
    acc[parent] = [child];
  } else {
    acc[parent].push(child);
  }
  if (!acc[child]) {
    acc[child] = [parent];
  } else {
    acc[child].push(parent);
  }
  return acc;
}, {});

const dfs = (start, target) => {
  const visited = Array(n + 1).fill(false);
  visited[start] = true;
  const stack = [[start, 0]];
  while (stack.length) {
    const [person, depth] = stack.pop();
    if (person === target) {
      return depth;
    }
    if (relations[person]) {
      relations[person].forEach(nextPerson => {
        if (!visited[nextPerson]) {
          visited[nextPerson] = true;
          stack.push([nextPerson, depth + 1]);
        }
      });
    }
  }
  return -1;
};

console.log(dfs(person1, person2));

relations에 인접 배열의 형태로 그래프를 나타내었다.

DFS를 통해 person1에서 person2까지 도달할 때 depth를 구하여 출력하였다.

만약 person2까지 도달하지 못하고 while문을 빠져나온다면 -1을 출력하도록 하였다.

 

 

💡 새로 알게 된 점

처음에 문제를 풀 때 DFS로 구하는 것이 최단거리를 보장할 수 있을 지 의문이었다.

가족/친척 관계라는 특성상 각 연결 요소들이 트리 형태의 자료 구조를 갖게 된다. 각 정점 간의 경로가 하나씩만 존재하기 때문에 방문한 경로가 곧 최단거리가 된다. 따라서 이 문제는 DFS로도 해결할 수 있는 문제다.