합승 택시 요금 [Lv. 3]

프로그래머스

목적지까지의 최소 비용을 구하는 문제입니다.

이때 목적지는 두개가 있으며 둘이 합승을 하여 비용을 아낄 수도 있습니다.

 

풀이 방법

이 문제의 핵심은 합승에 있습니다.

출발 노드(S)에서 합승해서 가는 노드(E) 까지의 최단 거리와

E노드에서 A, B로 가는 최단 거리를 더하고, 모든 경우의 수를 순회하여 최소 비용을 구하면 됩니다.

 

이렇게 하기 위해서는 우선 모든 노드에서 모든 노드까지의 최단 거리를 알 필요가 있습니다.

플로이드-워샬 알고리즘을 이용하여 모든 최단 거리를 찾고 합승해서 가는 노드를 모두 순회하여 문제를 풀면 됩니다

 

정답 코드

#include <string>
#include <vector>

using namespace std;
const int INF = 100000000;
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {

    vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));
    for (auto fare : fares)
    {
        int s = fare[0];
        int e = fare[1];
        int cost = fare[2];
        
        dp[s][e] = cost;
        dp[e][s] = cost;
    }
    
    for (int i = 1; i <= n; i++)
        dp[i][i] = 0; // 자기 자신은 거리가 0

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

    int answer = INF;
    for (int i = 0; i <= n; i++)
        answer = min(answer, dp[s][i] + dp[i][a] + dp[i][b]);
    	// [출발지 -> i노드(합승)] + [i노드 -> A지점] + [i노드 -> B지점]
        
    return answer;
}