[JS][백준]1916_최소비용 구하기

문제 번호

1916번: 최소비용 구하기

 

 

 

알고리즘 분류

• 그래프 이론
• 데이크스트라

 

문제 풀이

 모든 도시에서 모든 도시까지의 최소비용을 구하는 문제인 줄 알고 플로이드 와샬 알고리즘을 쓰려했으나 문제를 잘 읽어보니 A->B로의 최단거리만 구하면 되는 문제였다. 만약 플로이드와샬을 사용했었다면 O(N^3)의 시간 복잡도가 소요되므로 시간 초과에 걸렸을 것이다. 

 

 다익스트라알고리즘을 사용했다. 다익스트라의 시간 복잡도는 O(N*logN)이므로 시간제한인 0.5초 안에 들어오는데 무리가 없다. 

 

 문제의 조건을 살펴보니 서로다른 두 도시를 이동하는 버스가 1개라는 조건은 없었다. 그래서 문제에서 주어진 버스들의 정보를 입력받을 때 최소비용을 갖는 버스들만 입력받기로 하였다. 가령 X도시에서 Y도시로 가는 버스가 3대 있고 각각의 버스의 운행비용이 (10,5,1)이라면 A에서 B로 가는 버스는 1의 비용을 갖는 버스만 있다고 생각했다.

  let city = new Array(N + 1).fill(null).map(_ => new Array(N + 1).fill(Infinity));
  for (let i = 0; i < bus.length; i++) {
    let [from, to, cost] = bus[i];
    if (cost < city[from][to])
      city[from][to] = cost;
  }

 

 이제 다익스트라를 적용시키면된다. 우리가 원하는 건 A에서 B로 갈 때의 최소 비용이므로 A를 출발점으로 하여 다익스트라를 적용시키고, A에서 B까지의 최소비용이 얼마인지 확인해보면 된다.

 

 다익스트라를 구현하는 과정에서 최소힙을 사용하였다. 최소 힙을 구성하는 Node는 [현재 도시, 도착지, 비용]으로 구성되어있는데 도착지(to)는 다익스트라를 구동시키는데 필요하지 않았다.

 

전체 코드.

/**
 * A->B 로 가는 다익스트라?
 * 10^5 가지 정점. 도로가 여러개면 최소비용이 드는 도로정보만 남겨둔다.
 * MinHeap에 1000개는 넣을 수 있음.
 * 
 * 1. 각 도시별로 최소비용이 드는 버스정보만 담아서 2차원 배열을 완성한다.
 * 2. A->B로 가는 최소비용을 다익스트라를 이용해서 구한다.
 */
class Node {
  constructor(from, to, cost) {
    this.from = from;
    this.to = to;
    this.cost = cost;
  }
}
class MinHeap {
  constructor(compare) {
    this.heap = [];
    this.compare = compare;
  }
  empty() {
    if (this.heap.length == 0) return true;
    else return false;
  }
  top() {
    return this.heap[0];
  }
  push(from, to, cost) {
    let node = new Node(from, to, cost);
    this.heap.push(node);
    let curIdx = this.heap.length - 1;
    let curItem = this.heap[curIdx];

    while (curIdx > 0) {
      let parentIdx = Math.floor((curIdx - 1) / 2);
      let parentItem = this.heap[parentIdx];

      if (this.compare(parentItem.cost, curItem.cost)) break;

      this.heap[curIdx] = this.heap[parentIdx];
      curIdx = parentIdx;
    }
    this.heap[curIdx] = curItem;
  }
  pop() {
    let lastIdx = this.heap.length - 1;
    this.heap[0] = this.heap[lastIdx];
    this.heap.pop();

    if (this.heap.length >= 1) {
      let curIdx = 0;
      let curItem = this.heap[curIdx];
      while (curIdx < this.heap.length) {
        let leftIdx = curIdx * 2 + 1;
        let rightIdx = curIdx * 2 + 2;

        if (leftIdx >= this.heap.length) break;
        let leftItem = this.heap[leftIdx];
        let rightItem = rightIdx < this.heap.length
          ? this.heap[rightIdx]
          : null

        let nextIdx = rightItem !== null && this.compare(rightItem.cost, leftItem.cost)
          ? rightIdx
          : leftIdx;
        let nextItem = this.heap[nextIdx];

        if (this.compare(curItem.cost, nextItem.cost)) break;

        this.heap[curIdx] = this.heap[nextIdx];
        curIdx = nextIdx;
      }
      this.heap[curIdx] = curItem;
    }
  }
}
function main() {
  const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
  const [N, M] = [+input[0], +input[1]];
  let bus = input.slice(2, 2 + M).map(_ => _.trim().split(' ').map(Number));
  const [A, B] = input[M + 2].trim().split(' ').map(Number);

  let city = new Array(N + 1).fill(null).map(_ => new Array(N + 1).fill(Infinity));
  for (let i = 0; i < bus.length; i++) {
    let [from, to, cost] = bus[i];
    if (cost < city[from][to])
      city[from][to] = cost;
  }
  return console.log(sol(N, M, A, B, city));
}
function sol(N, M, A, B, city) {
  let dist = new Array(N + 1).fill(Infinity); // 최소거리 기록용 배열.
  dist[A] = 0;

  let MH = new MinHeap((a, b) => a < b);
  MH.push(A, A, 0);
  // for (let i = 0; i < city[A].length; i++) {
  //   MH.push(A, i, city[A][i]);
  // }

  while (!MH.empty()) { // to는 실제로 사용되지는 않는다.
    let cur = MH.top();
    let [curCity, to, cost] = [cur.from, cur.to, cur.cost];
    MH.pop();
    for (let i = 0; i < city[curCity].length; i++) {
      let nextCost = cost + city[curCity][i]; // curCity에서 i로 갈때 드는 비용.
      if (nextCost < dist[i]) {
        dist[i] = nextCost;
        MH.push(i, city[curCity][i].to, nextCost); // 다음도시, 다음도시와 연결된 다음도시, 비용.
      }
    }
  }
  return dist[B];
}
main();

특이사항

 MinHeap을 구현할때 const를 사용하지 않고 let을 많이 사용하는데, const를 사용하는 습관을 들여야겠다. const를 사용하여 내가 원하지 않는 변경이 일어났을 때를 대비할 수 있기 때문이다.