[C++] 프로그래머스 합승 택시 요금 - 플로이드 와샬/다익스트라

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

프로그래머스

풀이

시작 지점s와 도착 지점 a, b 를 연결하는 최소 비용 경로를 찾는 문제이다. 

각 정점 s, a, b(다익스트라) 또는 모든 노드(플로이드 와샬)에서 모든 노드로의 최단 거리를 구한 후, 임의의 노드를 선택해서, 해당 노드에서 s, a, b와 연결되는 최소 비용을 구하면 된다. 이렇게 하면 s-s, s-a, s-b 와 같이 합승을 하지 않는 경우 또한 검사할 수 있다.

구현은 플로이드 와샬이 더 간단하지만 시간 복잡도는 다익스트라가 훨씬 유리하다.

<플로이드 와샬>

1. 모든 정점에서 모든 정점으로의 최단 거리를 구한다. O(N^3)

2. 임의의 정점 i 에 대해 답을 최소 비용으로 갱신한다.

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

using namespace std;
#define INF 100000000
// 플로이드 와샬

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
 
    vector<vector<int>> map(n+1, vector<int> (n+1, INF));
    for (int i=1; i<=n; i++) map[i][i]=0;
    
    for (int i=0; i<fares.size(); i++){
        map[fares[i][0]][fares[i][1]] = fares[i][2];
        map[fares[i][1]][fares[i][0]] = fares[i][2];
    }
    
    for (int k=1; k<=n; k++){
        for (int i=1; i<=n; i++){
            for (int j=1; j<=n; j++){
                if (map[i][j] > map[i][k]+map[k][j]){
                    map[i][j] = map[i][k]+map[k][j];
                }
                    
            }
        }
    }
    // 시작점에서부터 임의의 정점 i를 거쳐 도착점에 갔을 때 최단거리 비교
    for (int i=1; i<=n; i++){
        if (map[s][i]==INF || map[i][a]==INF || map[i][b]==INF) continue;
        answer = min(answer, map[s][i]+map[i][a]+map[i][b]);
    }
    return answer;
}

 

<다익스트라>

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

using namespace std;
#define INF 100000000
// 다익스트라
vector<vector<int>> dist(3, vector<int> (201, INF));
vector<pair<int, int>> map[201];

struct Edge{
    int vex, cost;
    Edge(int a, int b){
        vex=a;
        cost=b;
    }
    bool operator<(const Edge& b) const {
        return cost > b.cost; 
    }
};

void dijkstra(int idx, int st)
{
    priority_queue<Edge> pq;
    pq.push(Edge(st, 0));
    dist[idx][st]=0;
    
    while (!pq.empty()){
        int now=pq.top().vex;
        int cost=pq.top().cost;
        pq.pop();

        if (cost > dist[idx][now]) continue;
        
        for (int i=0; i<map[now].size(); i++){
            int nvex = map[now][i].first;
            int ncost = cost + map[now][i].second;
            
            if (ncost < dist[idx][nvex]){
                dist[idx][nvex]=ncost;
                pq.push(Edge(nvex, ncost));
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    // 그래프
    for (int i=0; i<fares.size(); i++){
        map[fares[i][0]].push_back({fares[i][1], fares[i][2]});
        map[fares[i][1]].push_back({fares[i][0], fares[i][2]});       
    }
    // s, a, b를 시작점으로 해서 각 노드까지 최단거리 get
    dijkstra(0, s);
    dijkstra(1, a);
    dijkstra(2, b);
    // 시작, 도착점에서부터 임의의 정점 i를 분기점으로 하여 그래프를 이을 때 최단거리 비교
    for (int i=1; i<=n; i++){
        if (dist[0][i]==INF || dist[1][i]==INF || dist[2][i]==INF) continue;
        answer = min(answer, dist[0][i]+dist[1][i]+dist[2][i]);
    }
    return answer;
}