[백준] 1967번 트리의 지름 Javascript(NodeJs)

문제 링크

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

알고리즘: DFS,트리

문제 요약

트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 트리의 지름이라고 정의한다. 트리의 지름을 출력하는 문제

풀이 요약

각각의 노드 마다 가장 긴 거리의 값을 저장해놓고 부모 노드에서 자식 노드의 저장 해놓은 값을 이용한다.자식 노드가 2개 이상이라면 sort해서 가장 큰 값 그 다음으로 큰 값을 배열에 넣고 자식 노드가 1개 라면 그냥 그 값을 배열에 넣음. 자식 노드가 없다면 처리 x DFS를 다 돌리고 배열에 들어있는 값들중 max값을 출력하면 정답.

소스코드

const fs = require('fs');
let inputData = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let N = inputData[0].trim() * 1;
let tree_list = Array.from(Array(N+1), () => Array());
let tree_v = Array.from(Array(N+1), () => Array());
let max_node = new Array(N+1).fill(0);
let root = new Array(N+1).fill(true);

for(let i=1; i<inputData.length; i++) {
    let node = inputData[i].trim().split(' ').map(x=>x*1);
    tree_list[node[0]].push(node[1]);
    tree_v[node[0]][node[1]] = node[2];
    root[node[1]] = false;
}

let root_node;
for(let i=1; i<root.length; i++) {
    if(root[i]) {
        root_node = i;
        break;
    }
}
let answel = [];
if(N === 1) {
    console.log(0);
} else {
    DFS(root_node);
    console.log(Math.max(...answel));
}

function DFS(n) {
    if(tree_list[n].length === 0) {
        return;
    } else {
        let result = [];
        for(let i=0; i < tree_list[n].length; i++) {
            DFS(tree_list[n][i]);
            result.push(tree_v[n][tree_list[n][i]] + max_node[tree_list[n][i]]);
        }
        result.sort((a,b) => {
            return b-a;
        })
        max_node[n] = result[0];
        result.length >=2 ? answel.push(result[0] + result[1]) : answel.push(result[0]);
    }
}