[백준1916_자바스크립트(javascript)] - 최소비용 구하기

🔴 문제

최소비용 구하기

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');
const n = +inputs[0];
const m = +inputs[1];
const graph = Array.from({ length: n + 1 }, () => []);
const [start, end] = inputs.at(-1).split(' ').map(Number);

for (let i = 2; i < m + 2; i++) {
  const [s, e, c] = inputs[i].split(' ').map(Number);

  graph[s].push([e, c]);
}

const getMinNode = (distances, visited) => {
  let minDistance = Infinity;
  let minNode = -1;

  for (let i = 1; i <= n; i++) {
    if (!visited[i] && distances[i] < minDistance) {
      minDistance = distances[i];
      minNode = i;
    }
  }

  return minNode;
};

const dijkstra = (start, end) => {
  const distances = Array(n + 1).fill(Infinity);
  const visited = Array(n + 1).fill(false);
  distances[start] = 0;

  for (let i = 0; i < n; i++) {
    const currentNode = getMinNode(distances, visited);

    if (currentNode === -1) break;
    visited[currentNode] = true;

    for (const [nextNode, cost] of graph[currentNode]) {
      const distance = distances[currentNode] + cost;

      if (distance < distances[nextNode]) distances[nextNode] = distance;
    }
  }

  return distances[end];
};

console.log(dijkstra(start, end));

🟢 풀이

⏰ 소요한 시간 : -

내 첫 다익스트라 문제...! 이해하느라 진짜 너무 오랜시간이 걸렸다...ㅠ
심지어 처음엔 반드시 우선순위 큐를 써야하는 문제인지 알았는데 아니더라..
이 문제는 A도시에서 B도시로 가는 경우의 수만 확인해주면 되기 때문에 A도시 기준으로 다익스트라를 한번 수행해주면 된다.
다익스트라 로직은 이곳에서 더 자세히 설명해놨으니 참고하면 좋을듯하다

🔵 Ref

🌿 다익스트라 알고리즘 (최단경로 알고리즘)