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

문제 링크

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

알고리즘: DFS,트리

문제 요약

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 의미한다.트리의 지름을 출력해라.

풀이 요약

이 문제는 많이 헤맸던 문제이다. 처음 생각한 풀이는 모든 점을 DFS로 돌리는 방법 이 방법은 정점의 개수가 10만개이기 때문에 2초에 시간제한을 절대로 지킬 수 없다.그 다음으로 생각한 것은 루트 노드만 찾는다면 그 노드에서 트리의 지름을 구할 수 있다.먼저 임의의 점을 DFS에 넣고 돌리는데 거리를 계속 체크하면서 더 긴 거리를 가졌다면 max_obj를 갱신해준다.그렇게 탐색이 종료되면 결국에는 시작 노드가 max_obj에 저장돼있으며 그 값을 넣고 다시 DFS를 돌리면 트리의 지름을 구할 수 있다. DFS를 두 번 돌리는 발상이 생각해내기 어려운 문제

소스코드

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_dtc = Array.from(Array(N+1), () => Array()); //서로 다른 정점끼리의 거리.
for(let i=1; i<inputData.length; i++) {
    let input = inputData[i].trim().split(' ').map(x=>x*1);
    let a = input[0];
    let j=1;
    while(input[j] !== -1) {
        if(j%2 === 1) {
            tree_list[a].push(input[j]);
        } else {
            tree_dtc[a][input[j-1]] = input[j];
        }
        j+=1;
    }
}
let max_obj = {node: 0, dtc: 0};
let visited = new Array(N+1).fill(false);
visited[1] = true;
DFS(1,0)
visited[1] = false;
visited[max_obj.node] = true;
DFS(max_obj.node,0);
console.log(max_obj.dtc);

function DFS(n, sum) {
    if(sum > max_obj.dtc) {
        max_obj = {node: n, dtc: sum};
    }
    for(let i=0; i<tree_list[n].length; i++) {
        if(!visited[tree_list[n][i]]) {
            visited[tree_list[n][i]] = true;
            DFS(tree_list[n][i], sum + tree_dtc[n][tree_list[n][i]]);
            visited[tree_list[n][i]] = false;
        }
    }
}