[JS] 백준 1916번 : 최소비용 구하기 - 그래프이론, 다익스트라

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

1916번: 최소비용 구하기

 

다익스트라 문제이다.

최소힙을 구현했어야했지만 나는 queue을 이용해서 방믄하지않은 노드 중 가장 짧은 거리의 노드를 선택하는 기능을 넣어 구현했다.

https://ydoag2003.tistory.com/41

다익스트라 알고리즘

 

 

📋풀이방법

1. 첫 번째로 arr배열에 인덱스를 기준으로 값을 저장한다. 예를 들어 arr[1]에는 [1에서 갈 수 있는 도시, 비용] 값을 기록한다.

2. 두 번째로 우리가 원하는 출발 노드의 기준으로 다른 노드에  갈 수 있는 최단거리를 저장하는 배열 dist를 선언한다.

-dist는 모든 값을 Infinity로 초기화한다.

3. 세 번째로 노드에 방문했음을 표시하기 위한 visited배열을 선언한다.

-visited는 모든 값을 0으로 초기화한다.

4. 네번째로 큐를 이용하기위해 pq배열을 선언한다.

 -시작을 위해 아래 사항을 준비해야한다.

 - 1. dist 배열에 시작노드의 인덱스 값은 0으로 만들어준다.

-  2. visited배열에 시작노드의 인덱스 값은 1로 만들어준다.- 방문했음을 의미

-  3. pq에 [시작 인덱스, 거리 0 값] 을 넣어줌으로써 시작한다.

5. pq가 빌 때까지반복

6. pq의 값을 하나씩 꺼낸다. - A노드

7. A노드를 visited배열에 방문표시해준다.

8. A노드에서 인접한 노드를 탐색한다. -> arr배열에서 찾음

9. 탐색하면서 A노드 -> B 노드로 가는 거리를 현재 dist배열에서의 값과 비교해서 더 작은 값으로 바꿔준다.

이는 

현재노드까지의 거리 + 현재노드에서 인접한 노드까지의 거리 < 시작노드에서 인접한노드까지의 거리

를 비교하는것이다.

10. 이제 방문하지않은 노드들 중에서 가장 최단거리의 노드를 찾아서 다음노드로 정해야한다.

11.dist배열에서 현재 노드에서 인접하고, 방문하지 않은 노드들 중 가장 최단 거리를 가진 노드를 찾는다.

12. 만약 인접한 노드 중 가장 최단거리의 인접노드를 찾았다면 pq배열에 다음 값을 push해준다.

 - 다음 노드 : n

 - 현재 노드 -> 다음 노드까지의 가리 : dist[n];

 

 

 

🤟내 제출

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

let N = Number(input[0].split(" "));
let M = Number(input[1].split(" "));
let arr = Array.from({ length: N + 1 }, () => []);
for (var i = 0; i < M; i++) {
  const [u, v, w] = input[i + 2].split(" ").map(Number);
  arr[u].push([v, w]);
}
let [start, end] = input[M + 2].split(" ").map(Number);

let dist = new Array(N + 1).fill(Infinity);
const visited = new Array(N + 1).fill(0);
visited[0] = 1;
dist[start] = 0;
const pq = [[start, 0]];

while (pq.length) {
  //cur : 현재노드 , len : 시작노드에서 현재노드까지의 거리
  const [cur, len] = pq.shift();
  //방문했음을 표시
  visited[cur] = 1;
  //현재 노드에서 인접한 노드를 탐색
  for (const [v, w] of arr[cur]) {
    //현재노드까지의 거리 + 현재노드에서 인접한 노드까지의 거리 < 시작노드에서 인접한노드까지의 거리
    // 위가 성사되면 최단거리이므로 갱신해준다.
    if (len + w < dist[v]) dist[v] = len + w;
  }
  //시작노드의 최단거리를 저장해놓은 dist
  //dist에서 방문하지 않은 노드중에, 가장 짧은 거리의 노드를 선별한다.
  //우선순위 큐방식을 이용한 것이다.
  //즉 쉽게 말해서 dist를 1에서부터 완성해가면서 1에서 갈 수 있는 가장 짧은거리의 인접노드의 순서대로 진행해야한다.
  const n = dist.reduce((acc, _, idx) => {
    return dist[idx] < dist[acc] && !visited[idx] ? idx : acc;
  }, 0);
  //만약 갈 수 있는 가장 최단거리의 인접노드를 발견했다면
  //그 노드를 다음 순번으로 두고 1->선택한 노드의 거리를 넘겨준다.
  if (n) pq.push([n, dist[n]]);
}
dist.shift();
dist = dist.map((e) => (e == Infinity ? "INF" : e));
console.log(dist[end - 1]);

 

 

💢어려웠던 점

1. 다익스트라 문제가 많이 나오는 것 같다.-> 3번째 풀이지만 아직 완벽하게 기억해내지 못했다.

2. 현재는 queue를 이용했지만 원래는 우선순위 큐를 이용하는 것이 효율적이다.

-우선순위 큐를 숙지해놔야겠다.

3. 시작노드 K에서 갈 수 있는 인접노드들의 최단거리를 dist에 넣은 다음 우선순위를 정하는 방법을 파악하지 못했다. -> 복사해왔는데 인접노드 중 가장 최단거리에 있는 인접노드를 찾는 방법은 잘 외워두자.

 - 아래처럼 dist를 검사해서 우선순위 노드를 정하고 queue에 넣어야한다