[백준] 2644번: 촌수계산 (Node.js)

1. 문제

2644번: 촌수계산

 

2. 풀이 

const [N, targets, , ...relationships] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [p1, p2] = targets.split(' ').map(val => +val);
const graph = Array.from({ length: +N + 1 }).map(() => []);
const checked = Array.from({ length: +N + 1 }).fill(false);

// 그래프 정리
const initialize = () => {
  relationships.forEach(relation => {
    const [parent, child] = relation.split(' ').map(val => +val);

    graph[parent].push(child);
    graph[child].push(parent);
  });
};

// initialize 함수 호출 후 dfs 탐색
console.log(
  (() => {
    let steps = 0;

    initialize();

    const areRelated = (p1, p2, count) => {
      if (checked[p1]) return;

      checked[p1] = true;
      count += 1;

      if (graph[p1].includes(p2)) {
        steps = count;
        return;
      }

      graph[p1].forEach(fam => {
        if (checked[fam]) return;

        areRelated(fam, p2, count);
      });
    };

    areRelated(p1, p2, 0);

    return !steps ? -1 : steps;
  })()
);

 

2-1. 접근 방식 

 

initialize 함수를 통해 부모 자식 관계 정보를 기준으로 일종의 족보를 그렸다 (즉, 그래프를 입력 값 기준으로 초기화 함). 그래프는 2차원 배열이며, N만큼의 배열로 구성되어 있다. 추후 사람 번호를 토대로 인덱스에 접근하기 위해 첫 배열(index = 0)은 빈 상태로 뒀다. 

 

이후 areRelated 함수를 통해 요구한 두 사람의 촌수를 계산하기 위해 그래프를 DFS 탐색했다. p1을 기준으로 p1과 직속으로 연결된 사람 중 p2가 있는지 확인하고, 없으면 p1과 직속으로 연결된 사람을 동일하게 탐색했다. 한번 탐색할 때마다 count는 1씩 증가해줬고, 확인한 사람의 번호는 checked 배열을 통해 관리했다. (전형적인 DFS 구조)  

 

탐색이 완료되었는데도 촌수를 나타내는 steps 변수가 여전히 0이면 -1을, 아니면 steps 변수에 할당되어 있는 값을 출력했다.