트리의 지름

• https://www.acmicpc.net/problem/1967

문제풀이

dfs를 이용해서 풀었다.
특정 한 점에서 가장 먼 지점까지 가면, 그 가장 먼 지점은 원의 지름을 만드는 점 중 하나이다.
그래서 dfs로 지름의 한 점을 구하고, 구한 점으로부터 또 가장 먼 거리를 구하면 트리의 지름이 된다.

조심! 자바스크립트로 풀었는데, 재귀함수로 풀면 터진다.

소스코드

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

const N = +input[0];
const adj = Array.from(Array(N + 1), () => Array());
input.slice(1, N + 1).map((e) => {
  const [parent, child, cost] = e.split(" ").map((el) => +el);
  adj[parent].push([child, cost]);
  adj[child].push([parent, cost]);
});

const dfs = (start) => {
  const visited = Array(N + 1);
  const stack = [[start, 0]];
  let vertex = 0;
  let max = 0;
  while (stack.length) {
    const [start, total] = stack.pop();
    if (visited[start]) continue;
    const edges = adj[start];
    visited[start] = true;
    if (max < total) {
      max = total;
      vertex = start;
    }
    for (let i = 0; i < edges.length; i++) {
      const [next, cost] = edges[i];
      stack.push([next, total + cost]);
    }
  }
  return { vertex, max };
};

if (N === 1) {
  log(0);
  return;
}
log(dfs(dfs(1).vertex).max);