LeetCode Cheapest Flights Within K Stops (JavaScript), Dijkstra + BFS

링크 : https://leetcode.com/problems/cheapest-flights-within-k-stops/description/?envType=problem-list-v2&envId=9id5lube

문제 설명

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return **-1.

Example 1:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Example 3:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

Constraints:

• 2 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• flights[i].length == 3
• 0 <= fromi, toi < n
• fromi != toi
• 1 <= pricei <= 104
• There will not be any multiple flights between two cities.
• 0 <= src, dst, k < n
• src != dst

---

문제 풀이

특정 지점에서 특정 지점으로 가는 최소 비용을 구하는 문제로 다익스트라를 떠올릴 수 있다.

하지만 k횟수 라는 제한이 있기 때문에 일반적인 다익스트라로는 구현이 불가능하다.

그 이유는 다익스트라는 '비용'적인 측면에서 최적화하기 때문에 횟수라는 제한이 추가가되면 일반적인 다익스트라 알고리즘으로 해결을 할 수 없다. -> 이미 방문한 노드에 대해서 최적의 답을 정했기 때문에

 

해당 문제는 dijkstra + bfs를 활용하여 문제를 해결했다.

접근 방식

• graph : src -> dst로 가는 비용을 저장하는 배열
• distance : src로 부터 각 지점까지의 최소 비용을 저장하는 배열
  • 초기 src는 0으로 초기화 (자기 자신이기 때문에)
• k라는 횟수를 파악하기 위해 queue 배열을 사용
  • [src, cost, stops] : 시작 지점, 비용, 횟수를 저장
• 각 지점에서 최소 비용을 계산하는 로직은 dijkstra형태로 진행이 되고, 최소 횟수를 통해 검사하는 노드는 bfs 형태로 진행을 한다.
  • 즉, queue의 배열의 길이가 0보다 크다면 계속 해서 검사
  • 최소 비용은 일반적인 dijkstra에서 각 노드를 거쳐 최소비용이 되는지 검사하는 로직을 사용

/**
 * @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 graph = Array.from({length: n}, () => []);
    flights.forEach(([s, d, c]) => graph[s].push([d, c]));

    const distance = Array(n).fill(Infinity);
    distance[src] = 0;

    // src, cost, stops
    const queue = [[src, 0, 0]];

    while (queue.length > 0) {
        const [from, cost, stops] = queue.shift();

        for (const [nei, c] of graph[from]) {
            const totalCost = cost + c;
            if (totalCost < distance[nei] && stops <= k) {
                distance[nei] = totalCost;
                queue.push([nei, distance[nei], stops + 1]);
            }
        }
    }

    return distance[dst] === Infinity ? -1 : distance[dst];
};

---

결론

이 문제는 일반적인 '비용'에 중점을 둔 dijkstra형태가 아닌, 횟수가 포함되어 BFS 형태를 응용해서 풀어야 하는 문제이다.

핵심 동작

1. 최소 비용 구하기 : dijkstra

2. 탐색 : bfs