프로그래머스 - 합승 택시 요금(2021 KAKAO BLIND RECRUITMENT)

코드

#include <string>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
int cost[201][201];
int INF = 10000000;
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cost[i][j] = INF;
    for(int i=1; i<=n; i++)
        cost[i][i] = 0;
    for(int i=0; i<fares.size(); i++)
    {
        int v1 = fares[i][0];
        int v2 = fares[i][1];
        cost[v1][v2] = fares[i][2];
        cost[v2][v1] = fares[i][2];
    }
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
    int solo = cost[s][a] + cost[s][b]; //합승안하고 각자갔을 경우
    answer = solo;
    //합승할 경우
    for(int i=1; i<=n; i++) //어디서 내릴지?
    {
        int cost_sum = 0;
        if (i == s) continue;
        cost_sum += cost[s][i] + cost[i][a] + cost[i][b];
        answer = min(answer, cost_sum);
    }
    return answer;
}

 

플로이드 와샬 알고리즘을 적용하면 쉽게 풀 수 있는 문제였다. 

 

Vertex i에서 Vertex j로 가는데 드는 최소 비용을 모든 vertex에 대해서 구해놓고, 그 배열을 이용하여 문제가 요구하는 바를 충족시키는 해를 찾으면 된다.

 

우선 합승을 안하는 경우가 최소일 수도 있으므로 먼저 계산한 후, 합승하였을 경우를 고려한다.

 

합승하는 경우 두 가지 경우가 존재한다.

1) A와 B가 합승하여 A, B의 도착지가 아닌 다른 곳에서 멈춘 후 각자의 도착지로 택시를 타고 가는 경우

2) A와 B가 합승하여 A나 B의 도착지에서 멈춘 후 나머지 한 명의 도착지로 택시를 타고 가는 경우

 

따라서 "어디서 내릴지"를 기준으로 반복문을 작성하여 가장 최소가 되는 cost_sum을 구하면 된다.