[LeetCode] 787. Cheapest Flights Within K Stops

struct Data{
        int now, dist, cost;
        Data(int a, int b, int c){
            now = a;
            dist = b;
            cost = c;
        }
        bool operator<(const Data &b)const{
		    return cost<b.cost;
	    }
    };

    
class Solution {
public:
   
  
    
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<pair<int,int>> v[101];
        vector<pair<int,int>> ct(n+1,make_pair(INT_MAX, 100));
        
        for(int i=0; i<flights.size(); i++){
            v[flights[i][0]].push_back(make_pair(flights[i][1], flights[i][2]));
        }
        
        priority_queue<Data> pQ;
        pQ.push(Data(src,0,0));
        
        while(!pQ.empty()){
            Data data = pQ.top();
            pQ.pop();
            
            if(data.dist > k){
                continue;
            }
            
            
            for(int i=0; i<v[data.now].size(); i++){
                int next = v[data.now][i].first;
                int cost = data.cost + v[data.now][i].second;
                int cnt = data.dist+1;
                if(cost<ct[next].first){
                    ct[next].first = cost;
                    pQ.push(Data(next, cnt, cost));
                }
                else if(cnt < ct[next].second) {
                    ct[next].second = cnt;
                     pQ.push(Data(next, cnt, cost));
                }
                
            }
            
        }
        
          
        if(ct[dst].first!= INT_MAX)
            return ct[dst].first;
        else return -1;
    }
    
};

솔직히 요즘 알고리즘 문제 거의 안 풀었지만.. 이 문제는 집착때문에 종종 도전을 했었다.
그리고 뭔가 풀릴듯 말듯 하다가 도저히 모르겠어서 포기하기를 반복했는데, 오늘은 그냥 풀다가 풀이를 쳐봤다.
근데 풀이를 봐도 모르겠는게 문제였다.

다른 사람의 풀이에서 힌트를 얻은 건 구조체를 정의할 때 해당 지점까지 거쳐간 거점의 수까지 함께 저장하는 것이었다. 그렇게 계속 구조체마다 거친 거점수를 세팅하고 비교해주면, k값을 넘었을 때 탐색을 중단하도록 할 수 있다.

솔직히 코드도 난잡해보이고 그냥 제발 풀려라 하면서 submit만 20번은 누른 것 같다..

이 문제 비슷한 건 풀어봤는데, 거쳐간 거점의 갯수를 세는 게 골치 아팠는데,
구조체에 변수값을 저장해서 문제를 해결할 수 있다는 걸 경험했다.