합승 택시 요금

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

문제설명

밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. “무지”는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. “무지”는 “어피치”와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 “어피치”에게 합승을 제안해 보려고 합니다.

문제는 무지와 어피치가 중간지점(시작부터 같이 안탈 수 있음)까지 같이 탑승하고, 중간지점에서 각각의 집까지 택시를 탑승한뒤 무지와 어피치의 택시요금이 얼마인지 계산한다. 이때 택시요금의 최솟값을 찾는 문제이다.

제한사항

• 노드의 개수 ≤ 200

해결과정

노드의 개수가 200이므로, $O(N^3)$의 플로이드 와샬 알고리즘을 사용해도 $10^7$을 넘지않는다.

플로이드 와샬 알고리즘을 사용하여, 모든 노드에서의 최단거리를 구한다. 이후 모든 중간지점에 대한 택시요금을 계산하고, 최솟값을 찾는다.

소스코드

#include <bits/stdc++.h>
#define INF 987654321

using namespace std;

// start -> 중간지점
// 중간지점 -> A의 지점
// 중간지점 -> B의 지점
// 3개의 합

int dst[201][201];
void Init(){
    for(int i = 0; i<=200;i++)
        for(int j = 0; j<=200; j++){
            dst[i][j] = INF;
            if(i == j) dst[i][j] = 0;
        }
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    Init();
    for(const vector<int>& v : fares){
        dst[v[0]][v[1]] = dst[v[1]][v[0]] = v[2];
    }
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j<=n; j++){
                if(dst[i][k] == INF || dst[k][j] == INF || i == j) continue;
                if(dst[i][j] > dst[i][k] + dst[k][j]) dst[i][j] = dst[i][k] + dst[k][j];
            }
    int ans = INF;
    for(int mid= 1; mid<=n;mid++){ 
        if(dst[s][mid] == INF || dst[mid][a] == INF || dst[mid][b] == INF) continue;
        ans = min(ans, dst[s][mid] + dst[mid][a] + dst[mid][b]);
    }
    return ans;
}