[백준][DFS][난이도:중] 노드사이의 거리 (1240번)

1.  문제

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

 

2. 핵심요약

■ 문제유형 : 깊이우선탐색(DFS) 알고리즘

 

3. 문제풀이 접근

■ distance 벡터[리스트]를 사용하여 누적되는 비용을 계산한다.

 

4. JavaScript 코딩

// 로컬 환경에서 입력을 받을지, stdin에서 받을지 결정하는 변수
let isLocal = true;
 
let fs = require('fs'); // 파일 시스템 모듈을 사용하여 파일 읽기
let input;
 
// 로컬 환경일 경우 파일에서 입력을 읽어옴, 그렇지 않으면 stdin에서 읽어옴
if (isLocal) {
    input = fs.readFileSync('./1240.txt').toString().split('\n');   // 파일에서 입력 받기
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');   // stdin에서 입력 받기
}
 
// 첫 번째 줄: 노드의 개수(N)와 거리를 알고 싶은 노드 쌍의 개수(M) 입력 받기
let [n, m] = input[0].split(' ').map(Number);
 
// 그래프 초기화: 각 노드에 연결된 노드와 거리를 저장할 배열
let graph = [];
for (let i = 0; i <= n; i++) {  // index 0은 사용하지 않음
    graph[i] = [];              // 각 노드에 연결된 노드들을 저장할 배열 초기화
}
 
// 트리 상에 연결된 두 점과 거리를 입력 받아 그래프에 저장
for (let i = 1; i < n; i++) {
    const [s, d, c] = input[i].split(' ').map(Number);  // s: 시작 노드, d: 도착 노드, c: 거리
    graph[s].push([d, c]);  // s 노드에서 d 노드까지 거리 c로 연결
    graph[d].push([s, c]);  // d 노드에서 s 노드까지 거리 c로 연결 (무방향 그래프)
}
 
// 깊이 우선 탐색(DFS) 함수
const dfs = (graph, currNode, dist, visited, distance) => {
    // 현재 노드가 이미 방문된 노드라면 탐색 종료
    if (visited[currNode]) return;
 
    visited[currNode] = true;   // 현재 노드를 방문 처리
    distance[currNode] = dist;  // 현재 노드까지의 거리 기록
 
    // 현재 노드와 연결된 노드들을 탐색
    for ([nextNode, cost] of graph[currNode]) {
        dfs(graph, nextNode, dist + cost, visited, distance); // 연결된 노드로 재귀 호출
    }
}
 
// M개의 거리 요청에 대해 각각의 거리를 계산
for (let i = n; i < n + m; i++) {
    const [s, d] = input[i].split(' ').map(Number); // s: 시작 노드, d: 도착 노드
 
    // 방문 여부를 추적할 배열과 거리 배열 초기화
    let visited = new Array(n + 1).fill(false);     // 방문 여부 배열 (index 0은 사용하지 않음)
    let distance = new Array(n + 1).fill(0);        // 거리 배열 (index 0은 사용하지 않음)
 
    // 시작 노드(s)에서 DFS 시작, 거리 초기값은 0
    dfs(graph, s, 0, visited, distance);
 
    // 도착 노드(d)까지의 거리 출력
    console.log(distance[d]);
}