Cheapest Flights Within K Stops

굉장히 좋은 문제를 풀었다. 그래프 문제를 연습하면서 느낀건데..난 진짜 하나도 모르는 바보였다. 다익스트라가 뭔지는 알아도 제대로 된 이론도 몰랐고.

벨만포드, 플로이드 등 너무 모르는 알고리즘이 많은거같다.

아래는 내가 처음 적었던 코드였는데 당연히 틀렸다. 왜 틀렸냐면 내가 DFS 를 사용하기도 하였고 문제가 의도 했던 최단 경로를 찾는 방법이랑 한참멀었다. DFS 과정으로 최단 경로를 찾는다는것은 계속 해서 노드의 거리를 업데이트 해줘야 하기때문에 매우 힘들다.

Priority_queue 를 사용한 방법도.. 예전에는 통과 했던 코드가 이번에 테스트 케이스가 추가되면서 TLE 가 걸렸다.

이 내용은 나중에 조금 더 자세하게 다룰 예정이지만.

최소 priority_queue 의 경우는 애초에 최소 값을 그대로 따라가기 때문에 조건문에 가중치 비교를 해줄 필요가 전혀 없다. 그저, 딱 목적지에 도착했을때가 최단 경로인거다

이 중요한걸 내가 모르고 있었다... ㅠㅠ 그런데 첫번째 시도에서는 fail 이 나왔다. 왜냐면 정말로 많은 테스트 케이스가 주어졌을때, 최소 가중치만 따라가다가 destination 에 도착을 못해서 TLE가 걸렸기 때문이다. 그렇기 때문에 통과된 코드에서는 한번 더 최적화가 걸려있었다.

마지막에 priority_queue 가 아닌 일번 큐로 했을때는 모든 테스트 케이스가 통과 되었다.

일반 queue를 사용하게 될 경우, 모든 노드를 큐에 집어 넣어서 모든 노드에서의 최소값을 구할 수 있다. 최적화는 안되어 있겠지만 당장 모든 노트를 집어 넣고 비교를 하기때문에 결국 destination 에 도착할 거고 TLE 가 안걸린다

이렇게 상황 마다 다르게 최적의 경로를 구할 수 있다는 문제가 있어서 정말 신기했다. 의미 있는 문제고 더 집중해서 풀어볼 생각이다.

class Solution {
public:
    void dfs(int src, int dst, int k, int& step, int& currentPrice, vector<int>& nodeInfo, vector<vector<pair<int,int>>>& adj){

        for(pair<int,int>& p : adj[src]){
            int node = p.first, price = p.second; 
            int original = nodeInfo[node]; 
            if(nodeInfo[node] > currentPrice + price && step <= k){
                nodeInfo[node] = currentPrice + price; 
                dfs(node,dst,k,step+=1,currentPrice+=price,nodeInfo,adj); 
                step-=1;
                currentPrice-=price; 
            } 
        }
    }

public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<pair<int,int>>> adj(n); 
        vector<int> nodeInfo(n,INT_MAX); 
        for(vector<int>& v : flights){
            int from = v[0], to = v[1], price = v[2]; 
            adj[from].push_back({to,price}); 
        }

        int currentPrice = 0; 
        int step = 0; 
        nodeInfo[src] = -1; 

        dfs(src,dst,k,step, currentPrice,nodeInfo,adj); 

        return nodeInfo[dst] == INT_MAX ?  -1 : nodeInfo[dst]; 
    }
};

priority_queue (fail)

class Solution {
public:
    
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<pair<int,int>>> adj(n);
        for(vector<int>& f: flights){
            adj[f[0]].push_back({f[1],f[2]});
        }
        
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> Q; 
        Q.push({0, src,k+1}); 
        
        while(!Q.empty()){
            vector<int> top = Q.top(); 
            Q.pop(); 
            int d = top[0]; 
            int u = top[1]; 
            int e = top[2]; 
            if (dst == u) return d; 
            if (e > 0){
                for(pair<int,int> & v: adj[u]){
                    Q.push({d+v.second, v.first, e-1});
                }
            }
        }
        return -1; 
        
    }
};

priority_queue (success)

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<pair<int, int>>> adj(n);
        for (auto e : flights) {
            adj[e[0]].push_back({e[1], e[2]});
        }
        vector<int> stops(n, numeric_limits<int>::max());
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
        // {dist_from_src_node, node, number_of_stops_from_src_node}
        pq.push({0, src, 0});

        while (!pq.empty()) {
            auto temp = pq.top();
            pq.pop();
            int dist = temp[0];
            int node = temp[1];
            int steps = temp[2];
            // We have already encountered a path with a lower cost and fewer stops,
            // or the number of stops exceeds the limit.
            if (steps > stops[node] || steps > k + 1) continue;
            if (node == dst) return dist;
            for (auto& [neighbor, price] : adj[node]) {
                pq.push({dist + price, neighbor, steps + 1});
            }
        }
        return -1;
    }
};

일반 queue(success)

class Solution {
public:
    
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<pair<int,int>>>g(n);
        for(auto& i:flights) g[i[0]].push_back({i[1],i[2]});
        vector<int>dist(n,INT_MAX);
        dist[src]=0;
        queue<pair<int,int>>pq;
        pq.push({0,src});
        k+=1;
        while(!pq.empty() && k--){
            int n=pq.size();
            while(n--){
                int d=pq.front().first,s=pq.front().second;
                pq.pop();
                for(auto& i:g[s]){
                    if(dist[i.first]>d+i.second){
                        dist[i.first]=d+i.second;
                        pq.push({dist[i.first],i.first});
                    } 
                }                
            }
        }
        return dist[dst]==INT_MAX? -1:dist[dst];
        
    }
};