[백준] 1167번 트리의 지름 - JavaScript(NodeJS)

문제

1167번: 트리의 지름

풀이

트리의 지름을 구하는 문제이다.

트리의 지름을 구하는 방법

참고 사이트 -> 바로가기

 

해당 포스팅을 참고하면

 

임의의 정점 X에서 가장 먼 정점인 Y를 찾고
찾은 정점 Y에서 가장 먼 정점 Z를 찾는다.
이 Y부터 Z까지의 경로가 트리의 지름이다.

 

트리의 정보를 기반으로 임의의 정점에서 DFS나 BFS를 실행한 결과를 가지고
한번 더 실행해서 트리의 지름을 구해보자.

 

필자는 DFS를 이용하겠다.

 

주의할 점?

입력의 각 행이 "노드 다음노드 가중치 다음노드 가중치 .... -1" 로 주어짐을 유의한다.

방문을 판단하기 위해 체크 배열을 선언하고, 첫 DFS가 끝나면 다시 0으로 초기화한다.
두번째 DFS의 결과에서의 최대 거리 값이 트리의 지름이므로 출력한다.

 

코드는 다음과 같다.

 

코드

const sol = (input) => {
  const N = +input[0];
  input = input.slice(1);
  const tree = Array.from({ length: N + 1 }, () => new Array());

  input.map((str) => {
    const [node, ...nextInfo] = str.split(" ").map(Number);
    for (let i = 0; i < nextInfo.length - 1; i += 2) { 
      tree[node].push([nextInfo[i], nextInfo[i + 1]]);
    } // 각 행의 마지막 요소(-1)를 제외했고 (다음 노드, 거리) 쌍으로 입력을 받는다.
  });

  let check = Array.from({ length: N + 1 }, () => 0);
  let max = { node: 0, dist: Number.MIN_SAFE_INTEGER }; 
  // max 변수에는 최대 거리와 최대 거리인 노드가 들어간다.

  function dfs(node, dist) {
    check[node] = 1;
    if (max.dist < dist) max = {node, dist}; // 거리가 최대거리면 max객체의 노드, 거리 값을 갱신한다.
    for (let [nextNode, nextDist] of tree[node]) {
      if (check[nextNode]) continue;
      dfs(nextNode, dist + nextDist); // 다음 dfs에 거리 값을 더해준다.
    }
  }

  dfs(1, 0); // 임의의 노드(1번 노드 선택)에서 시작해서 첫 dfs를 실행
  max.dist = Number.MIN_SAFE_INTEGER;
  check = new Array(N + 1).fill(0); // check 배열 초기화

  dfs(max.node, 0); // 1번 노드에서의 최대 거리 노드인 max.node에서 시작해서 두번째 dfs 실행
  return max.dist; // 이 최대 거리 값이 실제 트리의 지름에 해당한다.
};

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });