백준) 2644 - 촌수계산 JS

📌 문제 링크

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

---

📌 문제 탐색하기

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

시간복잡도

• O(N + M)

알고리즘 선택

• DFS

---

📌 코드 설계하기

1. 문제의 input을 가져와 첫 번째 줄에서 전체 사람 수`n`을 가져옵니다.
2. 두 번째 줄에서 촌수를 계산할 두 사람의 번호를 가져옵니다.
3. 세 번째 줄에서 부모, 자식 관계의 개수를 가져옵니다.
4. 나머지 줄들을 부모, 자식 관계 배열로 변환합니다.
5. 정답을 저장할 변수 `answer`를 초기화 합니다.
6. 초기 깊이 `degree` 값을 설정합니다.
7. 방문 체크 배열을 생성하고 `false`로 초기화합니다.
8. 그래프를 표현할 2차원 배열을 생성합니다.
9. 양방향 그래프를 만듭니다
10. dfs함수를 정의 합니다.
    1. `start`는 현재 노드
    2. `depth`는 현재까지의 촌수
11. 목표 인물 `person2`에 도달하면 현재까지의 깊이를 정답으로 저장합니다.
12. 현재 노드와 연결된 모든 노드를 탐색합니다.
13. 방문하지 않은 노드라면 방문처리하고 해당 노드로 dfs를 실행 합니다.
14. 정답이 있으면 답을 출력하고 없으면 `-1`을 출력합니다.

---

📌 정답 코드

const fs = require('fs');
const filePath =
  process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input2.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');
const n = Number(input.shift());
const [person1, person2] = input.shift().split(' ').map(Number);
const m = Number(input.shift());
const relationships = input.map((x) => x.split(' ').map(Number));

let answer = 0;
const degree = 0;
const visited = Array(n + 1).fill(false);
const graph = Array.from({ length: n + 1 }, () => []);

relationships.forEach(([from, to]) => {
  graph[from].push(to);
  graph[to].push(from);
});

const dfs = (start, depth) => {
  if (start === person2) answer = depth;

  for (const v of graph[start]) {
    if (!visited[v]) {
      visited[v] = true;
      dfs(v, depth + 1);
    }
  }
};
dfs(person1, degree);
answer ? console.log(answer) : console.log(-1);