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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

해당 문제는 2021 KAKAO BLIND RECRUITMENT 기출 문제로 아래 사이트에 공식 해설이 있습니다.

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

 

무지와 어피치가 i지점까지 합승을 하고, i지점부터 a, b를 각자 이동할 때, 총 요금은 dist[s][i]+dist[i][a]+dist[i][b] 이다.

플로이드 와샬 알고리즘으로 특정 지점에서 특정 지점까지의 최단 거리를 모두 구하자.

i = 1부터 i = n까지에 대하여 dist[s][i]+dist[i][a]+dist[i][b]의 최솟값을 찾고 리턴하면 정답이다.

 

(참고하면 좋은 포스트: 최단거리구하기_플로이드 와샬(Floyd Warshall) 알고리즘)

 

 

팁

해당 문제를 다익스트라 알고리즘으로 푸는 방법도 있다.

플로이드 와샬 알고리즘이 특정 지점에서 특정지점까지의 모든 최단 거리를 구해준다면, 다익스트라 알고리즘은 특정 출발지로 부터 다른 지점까지의 최단거리를 구해준다.

출발지 S로 부터 다른 지점까지의 거리(distS), a로 부터 다른 지점까지의 거리(distA), b로 부터 다른 지점까지의 거리(distB)를 구한 뒤, distS[i] + distA[i] + distB[i] 의 최솟값을 구해 리턴하면 정답이다.

 

(참고하면 좋은 포스트: 최단거리구하기_다익스트라(Dijkstra) 알고리즘)

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cctype>
#include <climits>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using l = long long;
using ll = pair<l, l>;

#define X first
#define Y second

vector<vector<l>> dist(205, vector<l>(205, INT_MAX));

void Floyd(int n, const vector<vector<int>>& fares) {

    for (int i=1; i<=n; i++) dist[i][i] = 0;

    for (auto v : fares) {
        l c = v[0];
        l d = v[1];
        l f = v[2];
        dist[c][d] = min(dist[c][d], f);
        dist[d][c] = min(dist[d][c], f);
    }

    for (int k=1; k<=n; k++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {

    Floyd(n, fares);

    l mn = INT_MAX;
    for (int i=1; i<=n; i++) 
        mn = min(mn, dist[s][i]+dist[i][a]+dist[i][b]);
    return mn;
}