[C++/PGS] Lv.3 : 합승 택시 요금 (BFS/다익스트라)

 

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

---

프로그래머스 레벨 3

bfs로 최소경로 탐색하는 건 알겠는데,

합승 경로(S~p) + 합승지점부터 A까지 + 합승지점부터 B까지의 합의 최솟값을 구해야 하니

S~A, S~B의 최솟값을 구하고, 겹치는 부분을 빼면 되는건가? 싶었다.

하지만 뭔가 아닌 것 같아서,,,, 힌트를 참조했다 ㅎㅎ

 

알고 보니 다익스트라 알고리즘을 사용해서, [ S~p + A~p + B~p ] 거리의 최소합을 구하면 되는 문제였다!

S,A,B부터 출발해서 모든 점에 대한 최소 거리를 구한 다음,

거리의 합이 최소가 되는 지점을 구하면 답이 나온다.

 

아이디어 떠올리는게 어렵지만, 구현은 가중치 갱신만 신경써주면 된다.

 

 

나의 풀이

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <climits>
using namespace std;

vector<vector<pair<int,int>>> graph(201);

vector<int> bfs(int start){
    priority_queue< pair<int,int>, vector<pair<int,int>>, greater<> > pq;
    // 가중치(우선순위 내림차순), 노드
    vector<int> road(201,INT_MAX);
    pq.push({0,start});
    road[start] = 0;
    while(!pq.empty()){
        pair<int,int> p = pq.top();
        pq.pop();
        int nowNode = p.second;
        int nowCost = p.first;
        if(road[nowNode] < nowCost) continue;
        for(auto g:graph[nowNode]){
            if(g.first == start) continue;
            if(road[g.first] > g.second+nowCost){
                road[g.first] = g.second+nowCost;
                pq.push({road[g.first], g.first});
            }
        }
    }
    return road;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INT_MAX;
    // 최소비용 탐색 => 합승 경로(S~p) + 합승지점~A + 합승지점~B
    // 이 말은 즉, S~p + A~p + B~p 의 최소합.
    for(auto f: fares){
        int from = f[0];
        int to = f[1];
        int cost = f[2];
        graph[from].push_back({to, cost});
        graph[to].push_back({from, cost});
        // idx 출발, f1도착, 가중치 f2
    }
    vector<int> s_road = bfs(s);
    vector<int> a_road = bfs(a);
    vector<int> b_road = bfs(b);
    
    for(int i=0; i<201; ++i){
        if(s_road[i]==INT_MAX || a_road[i]==INT_MAX || b_road[i]==INT_MAX)
            continue;
        if(answer > s_road[i]+a_road[i]+b_road[i])
            answer = s_road[i]+a_road[i]+b_road[i];
    }
    
    return answer;
}