[백준] 트리의 지름 #1967

후기

풀이방법은 루트에서 먼저 dfs로 가장 먼 끝점을 찾았을 때, 반드시 그 점이 지름에 해당하는 두 점중의 한 점이 된다.
따라서 그 점을 찾고 그 점으로부터 한 번더 dfs를 돌려 최대 거리를 구해주면 된다.

c.f. 참고로 n이 1일 경우에는 지름을 0으로 생각해서 예외처리를 해줘야 한다.
(이것 때문에 런타임에러가 발생했다)

Node.js 풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = Number(input[0]);
const nodes = input.slice(1).map((v) => v.split(' ').map(Number));

class Node {
  prev = null;
  next = null;
  constructor(value) {
    this.value = value;
  }
}

const solution = (N, nodes) => {
    if (N === 1) return 0;
  const arr = Array.from(Array(N + 1), () => new Array());
  nodes.forEach(([n1, n2, dist]) => {
    arr[n1].push({ node: n2, dist });
    arr[n2].push({ node: n1, dist });
  });

  let maxDist = 0;
  let endPoint;
  const visited = new Array(N + 1).fill(false);
  const dfs = (node, curDist = 0) => {
    if (visited[node]) return;
    visited[node] = true;
    if (arr[node].length === 1 && visited[arr[node][0].node]) {
      // leaf 노드
      if (maxDist < curDist) {
        maxDist = curDist;
        endPoint = node;
      }
      return;
    }
    for (const nextNode of arr[node]) {
      dfs(nextNode.node, curDist + nextNode.dist);
    }
  };
  dfs(1);
  maxDist = 0;
  for (let i = 1; i <= N; i++) visited[i] = false;
  dfs(endPoint);
  return maxDist;
};

console.log(solution(N, nodes));