백준 node.js 16920번 트리의 지름 DFS

1167번: 트리의 지름

1. 다익스트라 알고리즘과 비슷하게 문제를 풀었습니다.
2. 차이가 있다면 다익스트라는 우선순위 큐를 구현하여 사용한다는 점이지만, 이번 문제 풀이에서는 DFS, 즉 Stack을 사용하여 문제를 풀어도 충분한 문제입니다.
3. 트리는 사이클이 없다는 점을 생각한다면 트리의 지름은 다음과 같이 구할 수 있습니다.
   1. 임의의 점 하나를 선택한 후, 그 점에서 가장 멀리 떨어져 있는 노드를 찾고, 그 노드에서 가장 멀리 떨어진 노드와의 거리가 트리의 지름입니다.

문제 풀이

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n");
const N = +input[0];

/*
  각 노드는 배열을 가지고 있다
  배열에는 다음노드에 대한 정보가 있다
  { next , distance }
*/
const nodes = Array.from({ length: N + 1 }, () => []);
for (let i = 1; i <= N; i++) {
  const [node, ...arr] = input[i].split(" ").map(Number);
  let index = 0;
  while (1) {
    const next = arr[index * 2];
    if (next === -1) break;
    const distance = arr[index * 2 + 1];
    index++;
    nodes[node].push({ next, distance });
  }
}

//가장 먼 노드를 찾는 함수
function findFarNode(number) {
	//number노드와의 거리를 distancArr에 기록합니다.
	//사이클이 없기 때문에 다익스트라 알고리즘이 필요 없지만 구현은 가능합니다.
  const distanceArr = Array(N + 1).fill(Infinity);
  const stack = [];
  stack.push(number);
  distanceArr[number] = 0;
  while (stack.length > 0) {
    const cur = stack.pop();
    for (let { next, distance } of nodes[cur]) {
      if (distanceArr[next] > distanceArr[cur] + distance) {
        distanceArr[next] = distanceArr[cur] + distance;
        stack.push(next);
      }
    }
  }
  let returnNode = 0;
  let returnDistance = 0;
  distanceArr.forEach((v,i)=>{
    if(v !== Infinity && v > returnDistance){
       returnNode = i
       returnDistance = v
      }
  })
  return [returnNode,returnDistance]
}

const [farNode,_] = findFarNode(1);
console.log(findFarNode(farNode)[1])