[JS] 백준 1753 : 최단경로 - 다익스트라

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

1753번: 최단경로

풀이방법

1. 다익스트라 문제이다.

2. DP문제 같으면서 그래프 문제이다.

3. 시작노드를 기준으로 시작해서

4. 갈 수 있는 인접노드를 탐색 후

  5. dist 배열에 그 인접노드 까지의 거리를 넣는다.

  6. 이때 만약 현재노드에서 인접노드까지의 거리가 시작노드에서 인접노드의 거리보다 짧다면

  7. dist를 짧은 거리로 갱신해준다

8. 갱신 완료 후 

9. 현재 완성된 dist를 검사해서 시작노드에서 갈 수 있는 노드 중에

10. 방문하지 않았고, 가장 최단거리의 노드가 있다면 -> 우선순위 선정

11. 그 노드를 다음 검사를 위한 노드로 정하고, 시작노드에서 그 노드 까지의 거리를 큐에 넣는다.

 

 

🤟내 제출

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 [V,E]=input.shift().split(" ").map(Number);
let K=Number(input.shift());

let arr = Array.from({length: V + 1}, _ => [])
for (let i = 0; i < E; i++) {
    const [u, v, w] = input[i].split(' ').map(Number)
    arr[u].push([v, w])
}
let dist = new Array(V + 1).fill(Infinity)
const visited = new Array(V + 1).fill(0)
visited[0] = 1
dist[K] = 0
const pq = [[K, 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.join('\n'))

 

 

💢어려웠던 점

1. 시작노드 K에서 갈 수 있는 인접노드들의 최단거리를 dist에 넣은 다음 우선순위를 정하는 방법을 파악하지 못했다.

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

 

 

 

---

하지만 속도 면에서 Heap 사용을 권장.

정점 V의 개수의 최댓값(20,000)이 증가할수록 Heap과 Queue의 속도 차이가 커짐.

 

 

힙(Heap)이란?

힙은 매우 힙한 자료구조다. 힙은 일종의 완전 이진 트리이다. 주로 우선순위 큐를 구현하는데 밑받침이 되는 자료구조로 쓰인다. 트리 구조이기 때문에 삽입과 삭제에 O(logN)의 시간이 소요된다.

힙은 최대힙(Max Heap) 또는 최소힙(Min Heap)으로 구분할 수 있고 빠른 시간 안에 최대값 또는 최소값을 찾아낼 수 있다. 주로 배열을 이용해서 이러한 힙 구조를 구현할 수 있는데, 보통 다른 언어의 경우에는 Heap 구조 자체를 기타 라이브러리를 통해 기본적으로 제공해주는 경우가 많다.

예를 들어 Java의 경우는 애초에 PriorityQueue 가 있으며, Python3의 경우에는 heapq 라던가 힙 구조화 시켜주는 heapify 함수 등이 있지만, 우리 JS는 당연히 이를 지원해주지 않는다... 😂

 

힙(Heap) 규칙

큐에는 FIFO, 스택은 FILO의 규칙이 있듯  힙(Heap)에도 규칙 있다. 

Heap Rule : 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 한다.

 

따라서, 원소를 추가하거나 삭제할때도 위의 규칙이 지켜져야 한다. 

배열로 나타낸 힙(Heap)

구현하기 전에 알아야 할 부분이 있다. 힙(Heap)은 트리를 배열로 나타낼 수 있다는 것이다. 

위 이미지에서 Min Heap은  [10, 15, 30, 40, 50, 100, 40], Max Heap = [100, 40, 50, 10, 15, 50, 40 ] 이 된다. 

배열로 인해 부모노드, 왼쪽, 오른쪽 자식 노드를 표현할 수 있다. 

 

Min Heap에서 6번째 index를 예로 들어보자.

현재 노드 Index = 6
부모 노드 :  Math.floor((자식 노드 Index -1) / 2 ) = 2
왼쪽 자식 노드 Index = (부모노드 * 2) + 1   =  5
오른쪽 자식 노드 Index = (부모노드 * 2) + 2  = 6

-현재 index가 6일때 누가 부모노드고, 자식노드인지 확인

			부모노드			왼쪽 자식 노드	현재노드, 오른쪽 자식 노드
Index	0	1	2	3	4	5	6
Node	10	15	30	40	50	100	40

 

힙에 대해 자세히 보기

https://chamdom.blog/heap-using-js/

[자료구조] JavaScript로 힙(Heap) 구현하기

 

Heap이용한 우선순위

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 [V,E]=input.shift().split(" ").map(Number);
let K=Number(input.shift());

let arr = Array.from({length: V + 1}, _ => [])
for (let i = 0; i < E; i++) {
    const [u, v, w] = input[i].split(' ').map(Number)
    arr[u].push([v, w])
}

//heap
const swap = (A, a, b) => ([A[a], A[b]] = [A[b], A[a]])
class Heap {
    constructor() {
        this.A = [0]
    }
    //가장 최단거리를 트리의 최상단(배열의 0번째값)으로 해주기 위한 up 수행
    //값이 mk(push)될 때 마다 수행한다.
    up(C) {
        const A = this.A

        const P = Math.floor(C / 2) //현재 들어온 인덱스의 부모노드 인덱스
        //현재 들어온 인덱스가 2보다 작거나 -> 부모노드가 없거나
        //부모노드가 있다면 부모노드의 거리값과 현재노드의 거리값을 비교
        //만약 현재노드값이 더작다면 ->우리는 현재 최단거리이므로 min heap임
        //아래 swap을 통해 둘이 바꿔줌
        if (C < 2 || A[C][1] > A[P][1]) return
        swap(A, P, C) //현재트리에서 부모노드와 자리를 바꾸고
        this.up(P) //바꾼 부모노드를 또 up해준다.-> 재귀를 통해 현재 요소가 상위요소보다 작을 때 까지 반복
    }
    // 추출알고리즘에서 최상위 노드를 가장 아래에있는 요소와 바꿔줬을 때
    // 여전히 heap의 규칙인지 확인해야한다.
    // 이때 위에서부터 제일 아래로 실행되는 Down함수 실행
    // 아래 rm에서 끝에있던 요소를 첫번째로 대체했었기 때문에
    down(P) {
        const A = this.A
        // 현재 요소를 맨위에 놓고 자식이 더 작다면 현재와 자식을 바꿔주는 down을 재귀로 반복

        //왼쪽 자식이 있는지 확인 ->왼쪽 노드를 기준으로 비교 검사할 것이기 때문에 왼쪽 노드가 있을 때까지 라는 조건을 넣어준다.
        if (2 * P > A.length - 1) return

        //자식요소가 있다면
        let C = 2 * P
        //2 * P + 1 : 왼쪽 자식노드
        // 2 * P + 1 < A.length  : 오른쪽 자식노드가 있고,
        // A[2 * P + 1][1] < A[2 * P][1] : 왼쪽보다 오른쪽 자식노드가 더 작으면
        //왼쪽 자식노드는 오른쪽 자식노드의 인덱스로 바꿔줌
        if (2 * P + 1 < A.length && A[2 * P + 1][1] < A[2 * P][1]) C = 2 * P + 1

        //만약 왼쪽 자식 노드가 배열을 벗어나거나
        //최상위 노드보다 크면 멈춤 -> 자식노드는 최단거리가 아니므로
        if (C > A.length - 1 || A[C][1] > A[P][1]) return
        
        //만약 최상위 노드보다 현재노드가 작으면 최상위 노드와 바꿔줌 ->자식노드가 더 최단거리이므로
        swap(A, P, C)
        //그리고 새로운 위치에서 비교를 위해 바꾼 노드를 다시 검사함
        this.down(C)
    }
    //삽입 알고리즘
    mk(x) {
        const A = this.A
        A.push(x)
        this.up(A.length - 1)//가장 최근의 들어온 값이므로 마지막 인덱스를 up으로 보내줌
    }
    //추출 알고리즘
    rm() {
        const A = this.A
        //배열의 크기가 2보다 작으면 자식노드가 없는거니까 가장 최상단요소가 추출됨
        if (A.length < 2) return 0
        //아니라면 가장 마지막 요소를 일단 뺌
        const end = A.pop()
        //뺐는데 1이면 현재 배열의 크기가 2인거니까 
        //뺐던거 온전히 추출해줌
        if (A.length == 1) return end
        //만약 1이아니면 배열은 3이상의 트리를 가지고 있는 것이므로
        //최상위 노드를 가장 아래에있는 요소로 대체한다.
        const [min] = A.splice(1, 1, end)
    
        this.down(1)
        return min
    }
}
const dist = new Array(V + 1).fill('INF')
dist[K] = 0
const HP = new Heap()
HP.mk([K, 0])
while (HP.A.length > 1) {
    const [cur, len] = HP.rm()
    
    if (len > dist[cur]) continue
    for (const [v, w] of arr[cur])
    if (len + w < dist[v] || dist[v] == 'INF') {
        dist[v] = len + w
        HP.mk([v, dist[v]])
    }
}
dist.shift()
console.log(dist.join('\n'))

 

https://velog.io/@89cynical/%EB%B0%B1%EC%A4%80-1753-nodejs

백준 1753 nodejs