[프로그래머스/C++] 합승 택시 요금

✅ LV.3

📌 2021 KAKAO BLIND RECRUITMENT

✏️ 최종 솔루션

⭐️ 다익스트라

1. 다익스트라로 모든 노드-노드 최소비용 구하기
2. answer 는 s-a 택시 값 + s-b 택시 값 으로 초기화
3. 모든 노드를 탐색하여 s-i 택시 값 + i-a 택시 값 + i-b 택시 값 중에 최소값 구하기

📌 self feedback

플로이드 워셜로 푸는 게 더 효율적이라지만 익숙하지 않아서 넘 어렵게 느껴져서 다익스트라로 풀이했다. 효율성 테스트 하나 통과 못할 뻔했지만 ios_base::sync_with_stdio(false) 명령어 써서 야매로 해결
이제 다익스트라 익숙해진 줄 알았지만 전혀 아니었고..

다익스트라 문제인 것 같다고 생각했지만 합승 구간을 어떻게 구해야할지 감이 오지 않았다..

🔗 🔗 다익스트라 알고리즘

✏️ 최종 code

#include <string>
#include <queue>
#include <iostream>
#include <vector>

using namespace std;

vector<pair<int,int>> dist[301];

int visit[301][301];

void dijikstra(int s) {
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    pq.push({0,s});

    while(!pq.empty()) {
        int cur=pq.top().second;
        int d=pq.top().first;
        pq.pop();
        
        for(int i=0;i<dist[cur].size();i++) {
            int next=dist[cur][i].first;
            int c=dist[cur][i].second;
            
            if(visit[s][next]>c+d) {
                visit[s][next]=c+d;
                pq.push({c+d,next});
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    ios_base::sync_with_stdio(false);
    
    int answer = 9000000001; 
    
    for(int i=0;i<fares.size();i++) {
        int nd1=fares[i][0];
        int nd2=fares[i][1];
        int c=fares[i][2];
        dist[nd1].push_back({nd2,c});
        dist[nd2].push_back({nd1,c});
    }
    
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(i==j) visit[i][j]=0;
            else visit[i][j]=9000000001;
        }
    }
    
    for(int i=1;i<=n;i++) {
        dijikstra(i);
    }
    
    int cnt=visit[s][b]+visit[s][a];
    for(int i=1;i<=n;i++) {
        // s 에서 i까지 합승
        cnt=visit[s][i]+visit[i][a]+visit[i][b];
        answer=min(cnt,answer);
    }
    
    return answer;
}