[BOJ] 1240 노드사이의 거리 (node.js)

BOJ 문제 1240번의 풀이 과정을 작성한 게시글입니다.

 

링크

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

 

문제

N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

 

풀이 과정

접근법 1. 플로이드 워샬

구하는 것은 주어진 M개의 쌍의 두 노드 사이의 거리를 구하는 것이다.

그렇다면 모든 노드간의 거리를 미리 구해놓고 M번의 알고싶은 노드에 대해 거리를 출력하면 되지 않을까 생각했다.

 

하지만 모든 노드간의 거리를 구할 때 사용하는 알고리즘인 플로이드 워샬은 시간복잡도가 O(n^3)이다.

이는 최대 노드가 1,000임을 고려했을 때, 최대 O(10^9)의 연산이 수행될 수 있으므로 시간초과가 발생할 수 있다.

 

따라서 다른 방법을 생각해야 한다.

 

접근법 2. bfs

각각의 정점(1~N번 까지)을 root 노드라고 간주하고 전체 정점을 순회하며 bfs를 돌려서 모든 정점을 탐색하는 방법을 떠올렸다.

 

전체 노드를 기준으로 하고, 전체 정점을 순회한다면 시간복잡도는 최대 O(10^6)이 될 것이기에 가능한 풀이이다.

 

 

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const [N, M] = input.shift().split(" ").map(Number);
const edge = input.splice(0, N - 1).map((x) => x.split(" ").map(Number));
const nodes = input.map((x) => x.split(" ").map(Number));

const graph = Array.from({ length: N + 1 }, () => []);

for (let [a, b, d] of edge) {
  graph[a].push([b, d]);
  graph[b].push([a, d]);
}

const dist = Array.from({ length: N + 1 }, () => Array(N + 1).fill(-1));

const bfs = (x) => {
  const visited = Array.from({ length: N + 1 }, () => false);
  visited[x] = true;

  const queue = [[x, 0]];

  while (queue.length > 0) {
    const [cx, cd] = queue.shift();

    for (let [nx, nd] of graph[cx]) {
      if (visited[nx]) continue;

      visited[nx] = true;
      dist[x][nx] = cd + nd;
      dist[nx][x] = cd + nd;
      queue.push([nx, cd + nd]);
    }
  }
};

for (let i = 1; i <= N; i++) {
  bfs(i);
}

const answer = [];

for (let [a, b] of nodes) {
  answer.push(dist[a][b]);
}

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

 

후기

 

문제를 풀고 다른 사람의 풀이를 보니, 다익스트라, bfs, dfs 등 다양한 풀이가 있는 듯 했다.