풀이방법은 루트에서 먼저 dfs로 가장 먼 끝점을 찾았을 때, 반드시 그 점이 지름에 해당하는 두 점중의 한 점이 된다.
따라서 그 점을 찾고 그 점으로부터 한 번더 dfs를 돌려 최대 거리를 구해주면 된다.
c.f. 참고로 n이 1일 경우에는 지름을 0으로 생각해서 예외처리를 해줘야 한다.
(이것 때문에 런타임에러가 발생했다)
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));
오옹 잘보고가요