다익스트라와 이진트리 (feat. min heap 구현)

다익스트라가 사용되는 때

알고리즘 접근법 중 다익스트라는 가중치가 있는 그래프에서 최소 비용 경로를 구할 때 주로 사용한다. 파이썬에서의 다익스트라는 큐에서 가장 최소값을 꺼내기 위해 내장 라이브러리인 heapq를 사용하면 됐었지만 기본 자바스크립트에서는 heap을 지원하지 않기 때문에 직접 구현해서 쓸 수 있다.

다익스트라의 구현

큐에서 가장 최소값을 꺼내기 위해 heap이 아닌 우선순위큐를 구현해서 할 수도 있지만, 두 방식은 시간 복잡도에 큰 차이가 있다.

구체적인 구현 방식을 서술해보자면, 우선순위 큐(Priority Queue)는 요소의 추가(삽입, push) 혹은 제거(꺼내기, pop)때 마다 정렬을 새로 해줘야 한다. 자바스크립트의 내장 sort는 N*logN 의 비용이 들고, 제거할 때 조차 배열의 가장 앞에서 꺼내는 shift를 사용하게 된다면 자바스크립트의 배열 구현 방식을 생각했을 때, 각 요소마다 주소를 옮기는 작업을 하게 될 것이므로 시간 복잡도는 더 증가한다.

PriorityQueue
- 삽입 시 전체 배열 재정렬 (sort, NlogN)
- (구현 방식에 따라) 꺼낼 때 전체 배열 요소의 이동 (N)

 

그러나, min heap을 구현한다면 이진트리를 사용하기 때문에 logN의 비용만 든다. min heap은 이진트리의 부모 노드가 자식 노드보다 작은 숫자를 보장한다는 특징을 활용해 구현한다.

MinHeap
- 삽입시 최하단 노드에 추가 후, 이진트리를 타고 올라가며 자리 조정 (logN)
- 꺼낼 때 루트 노드를 꺼내고, 최하단 노드를 올린다. 이후 끌어올린 노드를 자식 노드들과 비교하며 자리 조정 (logN)

 

Min Heap 의 구현

이진트리를 구현하는 방식에는 여러 가지 방법이 있겠지만, 그 중에서도 1차원 배열로 트리 구조를 구현하는 것이 꽤 흥미로웠어서 이를 그림으로 표현해봤다.

1차원의 배열이지만 각 인덱스의 관계성을 이용해 부모와 자식으로 접근한다는 점이 인상적이다. 

min heap 구현에서 새로 추가한 요소를 최하단에 넣고 트리를 타고 올라가면서(bubble up) 요소의 위치를 바꾸는 동작(swap)을 하는 과정에서, 부모 노드에 접근하는 구현이 필요하다. 이 때 parent = Math.floor( (children-1) / 2 ) 계산을 이용해 부모 노드 인덱스를 구해서 접근할 수 있다. 

또 반대로, 요소를 꺼냈을 때는 가장 상단 노드인 루트 노드에서 꺼내고 최하단의 자식 노드(예를 들어 6번 노드)를 루트로 이동하는 방식으로 구현한다. 루트에 넣고, 다시 이진트리 규칙에 맞게 6번 노드의 요소의 위치를 조정(bubble down)하게 되는데 이때 left_children = parent * 2 + 1, right_children = parent * 2 + 2 로 자식노드에 접근해서 swap할 수 있다.

 

((주요 액션 정도만 확인해보세요))

export default class MinHeap {
  constructor() {
    this.values = [];
  }

  enqueue(node, priority) {
    this.values.push([node, priority]);
    this.bubbleUp();
  }

  bubbleUp() {
    if (!this.values || this.values.length < 2) return;
    const target = this.values.at(-1);
    let targetIndex = this.values.length - 1;

    while (targetIndex > 0) {
      let parentIndex = Math.floor((targetIndex - 1) / 2);
      let parent = this.values[parentIndex];

      // 부모가 더 작으면 이동 X
      if (parent[1] < target[1]) {
        break;
      }

      this.swap(targetIndex, parentIndex);
      targetIndex = parentIndex;
    }
    return;
  }

  // 루트를 꺼내고, 마지막 자식을 루트로 올리고, 자리 조정 (bubble down)
  dequeue() {
    this.swap(0, this.values.length - 1);
    let result = this.values.pop();
    this.bubbleDown();
    return result;
  }

  // TODO: 조건문 개선 필요
  bubbleDown() {
    let targetIndex = 0;
    let target = this.values[targetIndex];
    while (targetIndex < this.size() - 1) {
      let left_child = targetIndex * 2 + 1;
      let right_child = targetIndex * 2 + 2;

      // 자식 노드가 없을 때
      if (left_child >= this.size()) {
        break;
      }

      if (right_child >= this.size()) {
        if (this.values[left_child][1] < target[1]) {
          this.swap(targetIndex, left_child);
          targetIndex = left_child;
          continue;
        }
        break;
      }

      if (
        target[1] < this.values[left_child][1] &&
        target[1] < this.values[right_child][1]
      ) {
        break;
      }

      let parentCandidate = null;
      if (!this.values[left_child] || !this.values[right_child]) {
        parentCandidate = !this.values[left_child] ? right_child : left_child;
      }

      if (this.values[left_child][1] < this.values[right_child][1]) {
        parentCandidate = left_child;
      } else {
        parentCandidate = right_child;
      }

      this.swap(targetIndex, parentCandidate);
      targetIndex = parentCandidate;
    }
  }

  swap(a, b) {
    [this.values[a], this.values[b]] = [this.values[b], this.values[a]];
  }

  size() {
    return this.values.length;
  }
}

let h = new MinHeap();
h.enqueue("A", 2);
h.enqueue("B", 1);
h.enqueue("C", 5);

 

 

---

 

MinHeap 을 이용해 다익스트라를 구현하는 코드 예시는 이렇다. 노드의 최소 비용을 구현하기 위한 후보들을 저장하는 Queue(변수명 q)를 MinHeap으로 사용하는 것을 확인할 수 있다.

import MinHeap from "./minHeap.js";
function solution(graph, start) {
  // {arrived_node:[cost, prev_node]}

  const dashboard = {};
  const INF = Number.MAX_VALUE;
  Object.keys(graph).forEach((node) => {
    dashboard[node] = INF; 
  });
  dashboard[start] = 0;

  const q = new MinHeap();
  // q = [[거리, 직전노드], [0, 'A']]
  q.enqueue([dashboard[start], start]);

  while (q && q.size() > 0) {
    const [current_dist, current_node] = q.dequeue();

    if (dashboard[current_node] < current_dist) {
      continue;
    }

    for (const adjacent in graph[current_node]) {
      const w = graph[current_node][adjacent];
      const dist = current_dist + w;

      if (dashboard[current_node] > dist) {
        dashboard[current_node] = dist;
        q.enqueue([dist, adjacent]);
      }
    }
  }

  console.log(dashboard);
}

const inputs = {
  A: { B: 9, C: 3 },
  B: { A: 5 },
  C: { B: 1 },
};

let r = solution(inputs, "A");
console.log(r);

 

 

- 참고 자료

도서 - 코딩테스트 합격자 되기. 이선협, 박경록 저.