refactor: 백준/특정 거리의 도시 찾기 - 최소 heap으로 변경

dididy · dididy · commit 94cbd788c241 · 2021-03-25T15:57:11.000+09:00
diff --git a/boj/18352(다익스트라).js b/boj/18352(다익스트라).js
@@ -1,20 +1,95 @@
 // 특정 거리의 도시 찾기
 // https://www.acmicpc.net/problem/18352
 
+class MinHeap {
+  constructor() {
+    this.nodes = [];
+  }
+
+  isEmpty() {
+    return this.nodes.length === 0;
+  }
+
+  insert(value) {
+    this.nodes.push(value);
+    this.bubbleUp();
+  }
+
+  bubbleUp(index = this.nodes.length - 1) {
+    if (index < 1) return;
+
+    const currentNode = this.nodes[index];
+    const parentIndex = Math.floor((index - 1) / 2);
+    const parentNode = this.nodes[parentIndex];
+
+    if (parentNode[1] <= currentNode[1]) return;
+
+    this.nodes[index] = parentNode;
+    this.nodes[parentIndex] = currentNode;
+    index = parentIndex;
+    this.bubbleUp(index);
+  }
+
+  extract() {
+    const min = this.nodes[0];
+    if (this.nodes.length === 1) {
+      this.nodes.pop();
+      return min;
+    }
+    this.nodes[0] = this.nodes.pop();
+    this.trickleDown();
+    return min;
+  }
+
+  trickleDown(index = 0) {
+    const leftChildIndex = 2 * index + 1;
+    const rightChildIndex = 2 * index + 2;
+    const length = this.nodes.length;
+    let minimum = index;
+
+    if (!this.nodes[rightChildIndex] && !this.nodes[leftChildIndex]) return;
+    if (!this.nodes[rightChildIndex]) {
+      if (this.nodes[leftChildIndex][1] < this.nodes[minimum][1]) {
+        minimum = leftChildIndex;
+      }
+      return;
+    }
+
+    if (this.nodes[leftChildIndex][1] > this.nodes[rightChildIndex][1]) {
+      if (
+        rightChildIndex <= length &&
+        this.nodes[rightChildIndex][1] < this.nodes[minimum][1]
+      ) {
+        minimum = rightChildIndex;
+      }
+    } else {
+      if (
+        leftChildIndex <= length &&
+        this.nodes[leftChildIndex][1] < this.nodes[minimum][1]
+      ) {
+        minimum = leftChildIndex;
+      }
+    }
+
+    if (minimum !== index) {
+      let t = this.nodes[minimum];
+      this.nodes[minimum] = this.nodes[index];
+      this.nodes[index] = t;
+      this.trickleDown(minimum);
+    }
+  }
+}
+
 function dijkstra(N, K, X, graph) {
   const visit = Array(N + 1).fill(Infinity);
-  const queue = [];
+  const heap = new MinHeap();
 
-  queue.push([X, 0]);
+  heap.insert([X, 0]);
 
   visit[X] = 0;
 
-  while (queue.length !== 0) {
-    queue.sort((a, b) => {
-      return a[1] - b[1];
-    });
-
-    const [vertex, weight] = queue.shift();
+  while (!heap.isEmpty()) {
+    const [vertex, weight] = heap.extract();
 
     if (weight > K) {
       continue;
@@ -23,7 +98,7 @@ function dijkstra(N, K, X, graph) {
     for (let i = 0; i < graph[vertex].length; i++) {
       if (weight + 1 < visit[graph[vertex][i]]) {
         visit[graph[vertex][i]] = weight + 1;
-        queue.push([graph[vertex][i], weight + 1]);
+        heap.insert([graph[vertex][i], weight + 1]);
       }
     }
   }
@@ -90,6 +165,10 @@ console.log(dijkstra(N, K, X, graph));
 
 자바스크립트에는 기본으로 제공되는 우선순위 큐 자료구조가 없어서 루프를 돌 때 마다 정렬하는 식으로 타협을 봤다.
 
+---
+
+루프돌때 정렬하는 부분에 최소힙을 적용할 수 있을까 싶어서 최소힙을 적용해봤는데 의도한대로 작동하였다.
+
 ## Retrospective
 
 */
