[프로그래머스 Lv3] 합승 택시 요금 - Javascript 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

---

문제

A, B가 택시를 이용할 때 예상 최저 택시 요금을 구하는 문제

 

생각

문제의 노드 수 n은 200으로 작기 때문에 플로이드–워셜 알고리즘(O(n^3))을 사용해도 된다.
하지만 우선순위 큐 기반 다익스트라 구현을 익히기 위해,
본인은 다익스트라 알고리즘을 사용하여 문제를 해결했다.

 

문제풀이

일반적인 다익스트라 문제는 하나의 시작점에서 각 목적지까지의 최단 거리만 구하면 충분하다.

하지만 이 문제는 A와 B가 합승할 수도 있고, 중간에 갈라져 따로 갈 수도 있기 때문에,
총 세 개의 출발점을 기준으로 거리를 알아야 한다.

• S → 모든 노드까지 최단거리(distS)
  (합승 구간)
• A → 모든 노드까지 최단거리(distA)
  (A가 혼자 가는 구간)
• B → 모든 노드까지 최단거리(distB)
  (B가 혼자 가는 구간)

k는 A와 B가 택시에서 함께 내리는 지점(분기되는 지점)을 의미한다.

• S → k까지는 합승
• k → A까지는 A만 이동
• k → B까지는 B만 이동

따라서 총 비용은 이렇게 계산된다:

distS[k] + distA[k] + distB[k]

 

시간 복잡도는 O(ELogV)이다.

 

코드

function PriorityQueue() {
  const heap = [];

  function swap(a, b) {
    [heap[a], heap[b]] = [heap[b], heap[a]];
  }

  function bubbleUp() {
    let i = heap.length - 1;

    while (i > 0) {
      let parent = Math.floor((i - 1) / 2);

      if (heap[parent][0] <= heap[i][0]) break;

      swap(parent, i);
      i = parent;
    }
  }

  function bubbleDown() {
    let i = 0;

    while (true) {
      let left = i * 2 + 1;
      let right = i * 2 + 2;
      let smallest = i;

      if (left < heap.length && heap[left][0] < heap[smallest][0]) {
        smallest = left;
      }
      if (right < heap.length && heap[right][0] < heap[smallest][0]) {
        smallest = right;
      }
      if (smallest === i) break;

      swap(i, smallest);
      i = smallest;
    }
  }

  return {
    push(item) {
      heap.push(item);
      bubbleUp();
    },

    pop() {
      if (heap.length === 1) return heap.pop();

      const top = heap[0];
      heap[0] = heap.pop();
      bubbleDown();

      return top;
    },

    isEmpty() {
      return heap.length === 0;
    },
  };
}

function dijkstra(N, s, graph) {
  const INF = Infinity;
  const dist = Array(N + 1).fill(INF);
  const pq = PriorityQueue();
  dist[s] = 0;
  pq.push([0, s]);

  while (!pq.isEmpty()) {
    const [curDist, cur] = pq.pop();

    if (curDist > dist[cur]) continue;

    for (let [next, cost] of graph[cur]) {
      const newDist = curDist + cost;

      if (newDist < dist[next]) {
        dist[next] = newDist;
        pq.push([newDist, next]);
      }
    }
  }

  return dist;
}

function solution(n, s, a, b, fares) {
  const graph = Array(n + 1)
    .fill()
    .map(() => []);

  for (const [a, b, cost] of fares) {
    graph[a].push([b, cost]);
    graph[b].push([a, cost]);
  }

  const distS = dijkstra(n, s, graph);
  const distA = dijkstra(n, a, graph);
  const distB = dijkstra(n, b, graph);

  let answer = Infinity;
  for (let k = 1; k <= n; k++) {
    answer = Math.min(answer, distS[k] + distA[k] + distB[k]);
  }

  return answer;
}