LeetCode 787 - Cheapest Flights Within K Stops (Medium)

문제

LeetCode - 787번

풀이 과정

최대 K 개의 경유지를 포함한다는 조건 아래에서 한 정점에서 목표 정점까지의 최단 경로를 구하는 문제입니다.

따라서 단일 정점 - 모든 쌍 최단 경로 알고리즘인 다익스트라 알고리즘 을 변형해서 문제를 해결하였습니다.

사실 간선 선택을 위해 우선순위 큐 도 사용하지 않아서 애매한 부분이 있지만
BFS + Dijkstra 의 유형이라고 생각하면 될 것 같습니다.

이 문제의 핵심은 k 개의 경유지를 어떻게 처리할 것인가 입니다.

기존의 다익스트라 알고리즘 은 이전에 발견되어 큐에 저장되어 있는 경로 중
더 짧은 경로가 발견되어 dist 가 갱신 되었을 경우 큐에서 이전에 발견된 경로가 pop 되어
처리할 차례가 되면 그냥 무시를 해주는 방식으로 처리를 해줬습니다.

하지만 이번 문제에서는 비록 비용이 더 들더라도 무시하지 말고 해당 경로를 통해
최대 k 개의 정점으로 방문 가능한 모든 지점을 파악해줘야합니다.

예를 들어 k = 1 일때 위와 같이 생간 그래프에서 0 -> 1 -> 2 로 가는 경로 값은 2 라는 사실을 알게 되었다고 해서
0 -> 2 로 가는 경로를 무시하게 되면 0 -> 2 -> 3 으로 가는 경로를 찾지 못하게 됩니다.

코드

/**
 * @param {number} n
 * @param {number[][]} flights
 * @param {number} src
 * @param {number} dst
 * @param {number} K
 * @return {number}
 */
var findCheapestPrice = function (n, flights, src, dst, K) {
  // 인접 리스트 생성
  const adj = new Map();
  for (let [frm, to, weight] of flights) {
    if (adj.has(frm)) adj.get(frm).push([to, weight]);
    else adj.set(frm, [[to, weight]]);
  }

  function dijkstra(start) {
    let q = [];
    let dist = new Array(n).fill(Infinity);

    q.push([start, 0, 0]);
    dist[start] = 0;

    while (q.length) {
      let [here, cost, move] = q.shift();

      if (move > K || !adj.get(here)) continue;

      for (let [there, weight] of adj.get(here)) {
        let nextDist = cost + weight;
        if (dist[there] > nextDist) {
          dist[there] = nextDist;
          q.push([there, nextDist, move + 1]);
        }
      }
    }

    return dist[dst];
  }

  let ans = dijkstra(src);
  return ans === Infinity ? -1 : ans;
};