알고리즘 문제 풀기

백준 1240 : 노드 사이의 거리 - javascript(트리)

Fo_rdang 2024. 9. 27. 16:12
반응형

문제 출처 

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

 

정답 풀이 

- 트리 구조 정의 : 입력으로 주어지는 간선 정보를 이용한다. 

- dfs 를 사용하여 탐색한다. 

 

정답 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
let [n,m] = input[0].split(' ').map(v => +v); 
let tree = Array.from({length: n+1}, () => [])

for(let i=1; i<n; i++){
    let [a,b,dis] = input[i].split(' ').map(v => +v)
    tree[a].push([b,dis])
    tree[b].push([a,dis])
    }


function dfs(node, target, distance, visited){
    if(node === target) return distance
    visited[node] = true; 
    
    for(let [next, dis] of tree[node]){
        if(!visited[next]){
          let result = dfs(next, target, distance + dis, visited)
          if(result !== -1) return result
        }
    }
    return -1 
}

for(let i=n; i<n+m; i++){
    let [start, end] = input[i].split(' ').map(v => +v)
    const visited = new Array(n+1).fill(false)
    let answer = dfs(start, end, 0, visited)
    console.log(answer)
   }
반응형