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

2021 카카오 코딩 테스트 문제입니다.

 

코딩테스트 연습 - 합승 택시 요금

문제 확인

 

그래프 탐색 응용문제입니다.

 

풀이

 

합승 후 무지, 어피치 중 한 사람이 내리는 지점을 i로 두면 총요금은 dist[i][start] + dist[i][무지] + dist[i][어피치] 가 됩니다.

다익스트라 혹은 플로이드 와샬 알고리즘을 이용하여 dist 값을 구한 후 요금의 최솟값을 찾아내면 됩니다.

플로이드 와샬 알고리즘은 O(n^3)이며 다익스트라 알고리즘을 사용하면 3 * O(n^2)이 되므로 다익스트라 알고리즘이 더 빠릅니다. 결과를 비교해 보면 다음과 같습니다.

 

코드

 

- 다익스트라

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef struct edge {
    int dist, cost;
    bool operator<(const edge &t)const {
        return dist < t.dist;
    }
    edge(int d, int c) :dist(d), cost(c) {};
}edge;
void dijkstra(vector<edge> vtx[201], unsigned dist[], int start) {
    priority_queue <edge, vector<edge>, less<edge>> que;
    que.emplace(start, 0);
    dist[start] = 0;
    while (!que.empty()) {
        int cur = que.top().dist, cost = que.top().cost;
        auto &cur_vtx = vtx[cur];
        que.pop();
        for (int i = 0; i < cur_vtx.size(); i++) {
            if (dist[cur_vtx[i].dist] > dist[cur] + cur_vtx[i].cost) {
                dist[cur_vtx[i].dist] = dist[cur] + cur_vtx[i].cost;
                que.emplace(cur_vtx[i].dist, dist[cur_vtx[i].dist]);
            }
        }
    }
}
int solution(int n, int start, int a, int b, vector<vector<int>> arr) {
    int res = 0x7fffffff;
    unsigned dist[3][201];
    memset(dist, -1, sizeof dist);
    vector<edge> vtx[201];
    for (auto &t : arr) {
        vtx[t[0]].emplace_back(t[1], t[2]);
        vtx[t[1]].emplace_back(t[0], t[2]);
    }
    dijkstra(vtx, dist[0], start);
    dijkstra(vtx, dist[1], a);
    dijkstra(vtx, dist[2], b);
    for (int i = 1; i <= n; i++) {
        if (dist[0][i] != -1) {
            int t = dist[0][i] + dist[1][i] + dist[2][i];
            res = res > t ? t : res;
        }
    }
        
    return res;
}
 
int main() {
    vector<vector<int>> arr = { {{2,6,6}, {6,3,7}, {4,6,7}, {6,5,11}, {2,5,12}, {5,3,20}, {2,4,8}, {4,3,9}} };
 
    printf("%d", solution(6, 4, 5, 6, arr));
 
}
 
 

- 플로이드 와샬

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
 
void floyd_warshall(vector<vector<int>> &arr, unsigned dist[][201], int n) {
    
    for (int i = 1; i <= n; i++)
        dist[i][i] = 0;
    for (auto &t : arr) {
        dist[t[0]][t[1]] = t[2];
        dist[t[1]][t[0]] = t[2];
    }
    for (int i = 1; i <= n; i++) 
        for(int s=1;s<=n;s++)
            if(dist[s][i]!=-1)
            for (int e = 1; e <= n; e++) 
                if(dist[i][e]!=-1)
                    if(dist[s][e] > dist[s][i] + dist[i][e])
                        dist[s][e] = dist[s][i] + dist[i][e];    
}
int solution(int n, int start, int a, int b, vector<vector<int>> arr) {
    int res = 0x7fffffff;
    unsigned dist[201][201];
    memset(dist, -1, sizeof dist);
    floyd_warshall(arr, dist, n);
    
    for (int i = 1; i <= n; i++) {
        if (dist[i][start] != -1) {
            int t = dist[i][start] + dist[i][a] + dist[i][b];
            res = res > t ? t : res;
        }
    }
 
    return res;
}
 
int main() {
    vector<vector<int>> arr = { {{2,6,6}, {6,3,7}, {4,6,7}, {6,5,11}, {2,5,12}, {5,3,20}, {2,4,8}, {4,3,9}} };
 
    printf("%d", solution(6, 4, 5, 6, arr));
 
}