백준 5972번 - js

<문제>

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

 

 

 

 

<문제 핵심>

1. 문제를 보면 시작노드 1을 기준으로 N번 노드까지 접근하며 최소비용을 구해야하는 문제이므로 다익스트라 알고리즘을 사용해야 한다. 그리고 두 개의 헛간에 하나 이상의 길이 있다는 것은 양방향 그래프를 의미한다. 그래서 그래프를 만들 때 양방향 그래프로 만들어야한다.

 

양방향 그래프

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

 

 

2. 처음에 이 문제를 풀었을 때 시간 초과가 났었다. 이후 원인을 파악해보았고 답은 다음과 같았다. queue.sort()를 사용하여 큐에 있는 노드들을 매번 정렬한 후, 가장 짧은 거리를 가진 노드를 선택하는 방식으로 진행했었는데 이렇게 되면 큐에 노드가 많이 쌓일경우 정렬에 소모되는 시간이 급격히 증가한다.

 

그래서 큐를 선형적으로 탐색하여 가장 짧은 거리를 가진 노드를 찾는 방식으로 적용했다. 그리고 가장 짧은 거리를 가진 노드를 찾았다면 큐에서 제거하였다. (이유: 노드의 최단 경로가 확정되었기 때문. 이미 최단 경로가 확정된 노드를 다시 처리할 필요가 없으므로 확실하게 제거 필요)

 

<전>

while (queue.length > 0) {
  queue.sort((a, b) => a[0] - b[0]); // 거리를 기준으로 정렬
  const [currentDist, currentNode] = queue.shift();
  // 이후 처리 로직...
}

 

<후>

let minIndex = -1;
    //현재 큐에 남아있는 노드 중에서 짧은 거리를 담기위한 변수
    let minDist = Infinity;

    for (let i = 0; i < queue.length; i++) {
      if (queue[i][0] < minDist) {
        minDist = queue[i][0];
        minIndex = i;
      }
    }

 

 

<전체 코드>

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

const [n, m] = input.shift().split(" ").map(Number);
const edges = input.map((line) => line.split(" ").map(Number));
let graph = Array.from({ length: n + 1 }, () => []);
let dist = Array.from({ length: n + 1 }, () => Infinity);
let visited = Array.from({ length: n + 1 }, () => false);

const startNode = 1;

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

const dijkstra = (startNode) => {
  let queue = [[0, startNode]];

  dist[startNode] = 0;

  while (queue.length > 0) {
    let minIndex = -1;
    //현재 큐에 남아있는 노드 중에서 짧은 거리를 담기위한 변수
    let minDist = Infinity;

    for (let i = 0; i < queue.length; i++) {
      if (queue[i][0] < minDist) {
        minDist = queue[i][0];
        minIndex = i;
      }
    }

    const [currentDist, currentNode] = queue[minIndex];
    queue.splice(minIndex, 1);

    if (visited[currentNode]) continue;
    visited[currentNode] = true;

    for (let [nextNode, weight] of graph[currentNode]) {
      const newDist = currentDist + weight;

      if (newDist < dist[nextNode]) {
        dist[nextNode] = newDist;
        queue.push([newDist, nextNode]);
      }
    }
  }
};

// 다익스트라 알고리즘 실행, 1부터 시작하겠죠
dijkstra(startNode);

// 최종 결과 출력 (목적지인 N번 노드까지의 최단 거리)
console.log(dist[n]);