[백준1753_자바스크립트(javascript)] - 최단경로

🔴 문제

최단경로

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[v, _], s, ...inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

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

for (const input of inputs) {
  const [u, v, w] = input;

  graph[u].push([v, w]);
}

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

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

  return minNode;
};

const dijkstra = (start) => {
  const distances = Array(v + 1).fill(Infinity);
  const visited = Array(v + 1).fill(false);

  distances[start] = 0;

  while (true) {
    const node = getMinNode(distances, visited);
    if (node === -1) break;
    visited[node] = true;

    for (const [v, w] of graph[node]) {
      if (distances[node] + w < distances[v]) {
        distances[v] = distances[node] + w;
      }
    }
  }

  return distances;
};

const ans = dijkstra(s)
  .slice(1)
  .map((it) => (it === Infinity ? 'INF' : it))
  .join('\n')
  .trim();
console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

다익스트라 기본예제
각 그래프 정보를 인접리스트 형태로 입력받아준다.
그 후 둘째줄에 주어진 시작위치로부터 다익스트라 로직을 수행해주면 된다.
다익스트라 함수 내부에선 최단거리 테이블과 방문 배열을 만들어준다. 다른 언어라면 그냥 우선순위큐 사용하면 됨..
그 후 비용이 가장 작은 노드를 getMinNode 함수를 사용해 가져와서 해당 노드를 방문처리 하고 노드와 연결된 다른 노드들의 최단거리를 갱신해주면 된다.

🔵 Ref