[LeetCode] 787. Cheapest Flights Within K Stops

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

Cheapest Flights Within K Stops - LeetCode

LeetCode - Cheapest Flights Within K Stops

문제 유형 : 다익스트라, bfs

문제 난이도 : Medium

 

문제

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.

 

n개의 도시가 있다. flights[i] = [from, to, price]의 형태로 되어 있다.

from에서 to로 가는 비용이 price라는 뜻이다.

 

src, dst, k가 정수로 주어진다. src에서 dst로 최대 k번의 경유로 가는 최소 비용을 구하시오.

방법이 없으면, -1을 반환하시오.

 

 

풀이

기본적인 bfs를 이용한 다익스트라 알고리즘을 사용하면 된다.

최대 k+1번의 이동을 할 수 있기 때문에, 각각 인접한 노드로 한 칸씩 이동하는 bfs가 적절하다.

graph[from] = [[to, price], [to, price]]의 형태로 flights를 읽어서 인접리스트를 만든다.

거리를 저장하는 배열 dist에는 1e9로 초기화시켰다가, 최단거리를 업데이트 하는 식으로 한다.

불필요한 탐색을 줄이기 위해, 최단거리가 없데이트 되지 않으면 큐에 넣지 않도록 한다.

dist[dst] 가 1e9이면 -1, 아니면 dist[dst]를 반환한다.

 

코드

C++

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        k++; // stops -> steps
        unordered_map<int, vector<pair<int, int>>> graph;
        for(const auto &flight : flights) {
            graph[flight[0]].push_back({flight[1], flight[2]});
        }

        vector<int> dist(n, 1e9);
        dist[src] = 0;

        queue<pair<int, int>> q;
        q.push({src, 0});

        while(!q.empty() && k > 0) {
            int qSize = q.size();
            for(int i = 0; i < qSize; i++) {
                auto curr = q.front();
                q.pop(); 

                for(const auto &next : graph[curr.first]) {
                    if(dist[next.first] <= curr.second + next.second) continue;
                    dist[next.first] = curr.second + next.second;
                    q.push({next.first, dist[next.first]});
                }
            }
            k--;
        }

        return dist[dst] == 1e9? -1 : dist[dst];
    }
};