백준 1240 < 노드사이의 거리 > JavaScript

📍문제 링크

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

1240번: 노드사이의 거리

 

📍알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 트리

- 너비 우선 탐색

- 깊이 우선 탐색

 

📍문제 풀이

- 간선에 가중치를 갖는 트리가 주어질 때, 테스트 케이스에서 주어지는 시작점부터 끝점까지의 거리를 구하라

 

- DFS를 활용한다- 거리를 계산하는 로직은 아래와 같다1️⃣정점의 갯수 + 1 만큼의 길이를 갖는 빈 배열 distance를 만든다 (계산의 편의상)2️⃣현재 정점의 이웃 정점들을 순회하며 distance[이웃 정점 번호] 에 현재 정점까지의 거리(= distance[현재 정점 번호]) + 가중치를 더해 나간다3️⃣이때, 이웃 정점 번호가 끝점과 같으면 바로 더한 값 distance[끝점 번호]을 출력한다

 

📍코드 (JavaScript)

const [in1, ...in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [N, M] = in1.split(" ").map(Number);

class WeightedGraph {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(name) {
    if (!this.adjacencyList[name]) this.adjacencyList[name] = [];
  }
  addEdge(v1, v2, weight) {
    this.adjacencyList[v1].push({ node: v2, weight });
    this.adjacencyList[v2].push({ node: v1, weight });
  }
  dfs(start, end) {
    const stack = [{ node: start }];
    const distance = Array.from({ length: N + 1 }, (_) => 0);
    const isVisited = { [start]: true };
    while (stack.length) {
      const currentVertex = stack.pop();
      this.adjacencyList[currentVertex.node].forEach((neighbor) => {
        if (!isVisited[neighbor.node]) {
          distance[neighbor.node] =
            distance[currentVertex.node] + neighbor.weight;
          if (neighbor.node === end) return distance[end];
          isVisited[neighbor.node] = true;
          stack.push(neighbor);
        }
      });
    }
    return distance[end];
  }
}

const tree = new WeightedGraph();
const answer = [];

for (let i = 1; i <= N; i++) {
  tree.addVertex(i);
}

for (let i = 0; i < N - 1; i++) {
  const [v1, v2, weight] = in2[i].split(" ").map(Number);
  tree.addEdge(v1, v2, weight);
}

for (let i = N - 1; i < N - 1 + M; i++) {
  const [start, end] = in2[i].split(" ").map(Number);
  answer.push(tree.dfs(start, end));
}

console.log(answer.join("\n"));