feat: [Med.] Cheapest Flights Within K Stops (JS/TS)

https://leetcode.com/problems/cheapest-flights-within-k-stops/description/

1. 문제분석
노드 1~100개, [from, to, 비용] flights[] -> 시작점 src, 목표점 dst, 경유수 제약 k -> 미존재시 -1

2. 풀어보기
[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], from 0 to 3, stops limit 1
-> 그래프화 {0:{1:100},1:{2:100,3:600},2:{0:100,3:200}}
-> 0->1(100) k=0 -> 1->2(200), 1->3(700) k=1 -> k가 꽉 차서, 700이 답

3. 슈도코드
flights[] 돌려서 -> ends_by_start{} 만듦 -> ends는 {end:비용}
acc_from_src_by_end{} 만듦 -> {src:0, 나머지ends:무한}
Heap[]에 [end,acc] -> [src,0] -> BFS 돌려서 -> 매번 acc_pq min값 pop -> next가 없거나, k번 넘으면 끝
 -> 있으면, ends의 acc을 계산해서 -> acc_from_src_by_end에 업데이트 쳐줌 (기존값 보다 작으면)
다 끝났을 때 -> acc_from_src_by_end.dst 리턴 -> 이게 무한이면 -1

위 방법은, 망통인 경로의 비용이 더 낮았을 경우, 낙인이 찍혀서 더 높은 비용으론 진입할 수 없게 됨
-> 되돌아 나오면서 acc_from_src_by_end의 값을 복구해야 함 -> temp 스택 활용? -> 일단 킵.
acc_from_src_by_end[] 없이 -> k만 고려해서 acc_pq에 밀어넣고 -> k === acc_pq.min일 때의 비용 리턴
-> visited_by_end{start:limit} -> 방문하지 않았거나, 방문한 limit가 높을 때만 밀어넣음

-> acc_pq에서 pop 되는 시점에 visited_by_end.set

4. 구현코드

type From = number;
type To = number;
type Limit = number;

const by_value_asc = (a: [To, number, Limit], b: [To, number, Limit]) => a[1] < b[1];

const findCheapestPrice = (n: number, flights: [From, To, number][], src: From, dst: To, k: Limit): number => {
  const ends_by_start = parseGraph(flights);

  const cost = byDijkstra(ends_by_start, src, dst, k);
  return cost === Number.MAX_SAFE_INTEGER ? -1 : cost;
};

const byDijkstra = (ends_by_start: Map<From, Map<To, number>>, src: From, dst: To, k: Limit) => {
  const acc_pq = new Heap<[To, number, Limit]>(by_value_asc);
  acc_pq.push([src, 0, 0]);
  const visited = new Map<number, number>();

  while (acc_pq.size() > 0) {
    const [start, acc_to_start, limit] = acc_pq.pop()!;
    visited.set(start, limit);

    if (start === dst) {
      return acc_to_start;
    }

    if (limit <= k) {
      const ends = ends_by_start.get(start)?.entries() ?? [];

      for (const [end, cost] of ends) {
        const visited_limit = visited.get(end);

        if (!visited_limit || limit < visited_limit) {
          const acc_to_end = acc_to_start + cost;
          acc_pq.push([end, acc_to_end, limit + 1]);
        }
      }
    }
  }

  return -1;
};

const parseGraph = (flights: [From, To, number][]) => {
  const gparh = new Map<From, Map<To, number>>();

  for (const [start, end, cost] of flights) {
    const ends = gparh.get(start) ?? new Map<To, number>();
    ends.set(end, cost);
    gparh.set(start, ends);
  }

  return gparh;
};

class Heap<T>; // 힙 구현은 https://ha2el.tistory.com/23 참고

5. 풀이회고

이전문제와 같은 방법으로 풀려고 했는데, k 제약이 생각보다 까다로웠다.

경로가 (정답이 아닌) 망통이면 백트래킹을 하면서 되돌려줘야 하는데, 스택이 아닌 우선순위큐 기반이어서..

temp 스택을 활용하는 방안까지 생각 해보고, Solutions 참고해서 마무리했다.

우선순위큐에 일단 다 밀어넣고, 돌릴 때 나온 min값이 k일 때 -> 그 비용이 곧 정답인 걸로.

k에 대한 모든 경로의 비용이 다 들어가 있을 것이고.. visited를 통해 불필요한 경로를 솎아내는 로직이다.

일단은 이 문제도 하나의 유형으로 보고.. 최단거리 문제를 만나면 하나의 옵션으로 생각해보도록 하자.