백준 1167: 트리의 지름 - javascript(dfs)

문제 출처 

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

 

정답 힌트 

1. 임의의 노드에서 가장 먼 노드를 찾는다. 

2. 해당 노드에서 또 먼 노드를 찾고 그때의 거리가 트리의 지름이 된다. 

정답 코드 

const sol = (input) => {
    const N = +input[0]; 
    input = input.slice(1)
    const tree = Array.from({length: N+1}, () => new Array()); 
    
    input.map((str) => {
        const [node, ...nextInfo] = str.split(" ").map(Number); 
        for(let i=0; i<nextInfo.length - 1; i+=2){
            tree[node].push([nextInfo[i], nextInfo[i+1]])
        }
    }); 
    
    let check = Array.from({length: N+1}, () => 0); 
    let max ={node: 0, dist: 0}
    
    function dfs(node, dist){
        check[node] = 1 
        if(max.dist < dist) max = {node, dist}
        for(let [nextNode, nextDist] of tree[node]){
            if(check[nextNode]) continue; 
            dfs(nextNode, dist + nextDist)
        }
    }
    
    dfs(1, 0)
    max.dist = 0 
    check = new Array(N+1).fill(0)
    
    dfs(max.node, 0)
    return max.dist; 
}

const input = []; 
require('readline')
    .createInterface(process.stdin, process.stdout)
    .on("line", (line) => {
    input.push(line); 
})
    .on("close", () => {
    console.log(sol(input)); 
    process.exit(); 
})

 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const n = Number(input.shift())
const arr = input.map(line => line.trim().split(' ').map(Number))

function solution(n,arr){
    let tree = {}
    
    for(let i=0; i<n; i++){
        let key = arr[i][0]
        tree[key] = []; 
            for(let j=1; j<arr[i].length-1; j+=2){
                tree[key].push([arr[i][j], arr[i][j+1]])
            }
    }
    let checked = new Array(n+1).fill(false)
    let max = {node : 0, dist : 0 }
    
    dfs(1,0)
    checked = new Array(n+1).fill(false)
    max.dist = 0; 
    
    dfs(max.node, 0)
    return max.dist
    
    function dfs(node, dist){
        checked[node] = true; 
        if(max.dist < dist) max = {node, dist}
        
        for(let [nextNode, nextDist] of tree[node]){
            if(checked[nextNode]) continue; 
             dfs(nextNode, dist + nextDist)
        }
    }
}

console.log(solution(n,arr))