프로그래머스 - 합승 택시 요금

문제

한 명은 a 지점으로 가고, 한 명은 b 지점으로 가는데,
적당히 합승을 하면서 최소 비용으로 집에 가는 법을 구해라

생각

a 지점에서 모든 점 까지의 최소 거리, b 지점에서 모든 점 까지의 최소 거리를 구해놓고
어디 어디 에서 쪼개질 때 그 쪼개진 지점에서 a, b까지의 최소 거리를 구해야겠다~
까지는 쉽게 생각했는데.. 하는 동안 조금씩 문제가 있었다

문제 1

bfs를 사용해서
한 지점에서 합승을 그만두기도 하고
다른 지점으로 퍼져나가기도 하는 식으로 구현을 했다

    //시작점에서 퍼지면서 여기서 쪼개져보고 저기서 쪼개져보면서 최저 값 찾기
    queue<pair<int, int>> q; //지금 지점, 지금까지 돈
    int check[205] = {0, };
    q.push({s,0});
    
    int answer = cost[s][0] + cost[s][1];
    
    while(!q.empty()){
        int nowNode = q.front().first;
        int nowCost = q.front().second;
        q.pop();
        
        //여기서 쪼개져도 보고
        answer = min(answer, nowCost + cost[nowNode][0] + cost[nowNode][1]);
        
        //다른 곳으로 넘어가기도 하구
        for(auto i:info[nowNode]){
            if(check[i.second]==0){
                check[i.second] = 1;
                q.push({i.second,nowCost+i.first});
            }
        }
    }

처음엔 이게 왜 틀리는 지 몰랐는데,
어느 점까지의 최소 거리를 bfs로 퍼져서 구할 수 없어서 그런거였다!
(최단 거리 알고리즘이 따로 있는건 알았는데..
이 문제는 어디까지 가다가~ 합승 그만~ 이렇게 생각하고 그냥 bfs를 써버렸음..)

그래서 시작 지점에서 모든 지점까지의 최단 거리도 미리 구해놓고

    for(int i = 1;i<=n;i++){
        answer = min(answer, cost[i][0] + cost[i][1] + cost[i][2]);
        cout << i << " " << cost[i][0] + cost[i][1] + cost[i][2] << "\n";
    }

이렇게 구현해줬다..! 훨씬 간결하고 깔끔하고 좋구만..

문제 2

그냥 문제의 예시만 보고 아 최단 경로는 MST로도 구할 수 있겠구나!
이미 최소 길이로 온 곳을 다른 지점에서 또 올 필요가 없으니까~~
이러면서 프림으로 풀었는데, 테케를 엄청 틀리는 것..!

그래서 알아보니까 프림으로는 한 점에서 모든 최단 거리를 구 할 수 없다고 한다
그렇구나~~ 그래서 다익스트라 사용했음!

코드

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

using namespace std;

vector<pair<int, int>> info[205]; // index에서 first로 가는데 second만큼의 weight

int cost[205][3]; //a, b, s점에서의 모든 점의 거리 저장

void dijkstra(int startNode, int flag){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int check[205] = {0, };
    
    //시작점은 거리 0!
    cost[startNode][flag] = 0;
    //큐에 들어가서 퍼질 준비 됐으니까 1로 바꿔줘!
    check[startNode] = 1;
    pq.push({0, startNode});
    
    while(!pq.empty()){
        int nowNode = pq.top().second;
        int nowWeight = pq.top().first;
        pq.pop();
        
        for(auto i:info[nowNode]){
            int nextNode = i.second;
            int nextWeight = nowWeight + i.first;
            
            if(check[nextNode]==0){
                check[nowNode] = 1;
                // 현재 노드로 부터 연결된 엣지의 목적지까지 가는 거리와
                // 기존의 거리를 비교하여, 기존의 것이 더 크면 값을 갱신하고 더 탐색
                if (nextWeight < cost[nextNode][flag]) {
                    cost[nextNode][flag] = nextWeight;
                    pq.push({ nextWeight, nextNode });
                }
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    //간선 정보를 인접 행렬로 저장
    for(vector<int> f: fares){
        info[f[0]].push_back({f[2], f[1]});
        info[f[1]].push_back({f[2], f[0]});
    }
    
    //다익스트라를 위해 거리를 아주 크게 초기화
    for(int i = 0;i<3;i++){
        for(int j = 1;j<=n;j++){
            cost[j][i] = 2000000000;
        }
    }
    
    //a집에서 모든 점의 거리, b집에서 모든 점의 최소 거리를 다익스트라로 구해!
    dijkstra(a, 0);
    dijkstra(b, 1);
    dijkstra(s, 2);
    
    int answer = cost[s][0] + cost[s][1];
    for(int i = 1;i<=n;i++){
        answer = min(answer, cost[i][0] + cost[i][1] + cost[i][2]);
        cout << i << " " << cost[i][0] + cost[i][1] + cost[i][2] << "\n";
    }
    
    return answer;
}