[LeetCode] 787. Cheapest Flights Within K Stops

bin1225·2022년 8월 16일
0

Algorithm

목록 보기
2/70

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번은 누른 것 같다..

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

4개의 댓글

comment-user-thumbnail
2022년 8월 16일

내 블로그에 그래프 관련 문제를 보면은 구조체를 만들어서 푸는거를 종종 확인 할 수 있는데 BFS 류의 탐색을 할때 되게 유용하다! 살짝 어려운 문제 추천해준 거였는데 20번이나 누를 정도로 집착했다니 아주 뿌듯하구나...풀이를 보는것을 절대 부끄럽게 생각하지 말았으면 한다 ㅎㅎ

1개의 답글
Powered by GraphCDN, the GraphQL CDN