2021 KAKAO BLIND RECRUITMENT - 합승 택시 요금

이 문제는 택시비를 간선 간의 거리로 보면 그래프 상에서 최단거리를 구하는 문제로 생각해 볼 수 있다. 주요 포인트는 두 사람 A와 B가 합승을 통해 전체 비용을 단축시킬 수 있다는 것이다. 최소비용으로 A와 B 각자의 목적지에 갈 수 있는 경우는 두 가지 경우로 나눠볼 수 있다.

 

1. 합승해서 같이 임의 지점까지 최단 비용으로 이동한 후, 여기서 각자의 목적지를 향해 최단 비용으로 가기
2. 합승을 하지 않고 시작점 s에서 각자의 목적지를 향해 최단 비용으로 가기

두 가지 경우의 비용을 비교해서 더 작은 비용이 답이 될 것이다. 1번 방법의 최소 비용을 구하기 위해서는 시작점 s에서 임의의 지점까지 가는 최소 비용과 함께, 이 지점에서 각자의 목적지까지 가는 최소비용이 필요하다. 마침 지점의 갯수 n의 최대값도 200이므로, 플로이드 와샬 알고리즘을 사용해 모든 지점에서 다른 모든 지점까지의 최소 비용을 구한 뒤, 이를 이용해 답을 구할 수 있었다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
const int INF=1e9;
int dist[201][201];
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int i, j, k, answer = 0;
        
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++) dist[i][j]=INF; // 거리 초기화
    }
    
    for(auto fare : fares){
        dist[fare[0]][fare[1]]=fare[2];
        dist[fare[1]][fare[0]]=fare[2];
    }

    // 플로이드 와샬 알고리즘
    for(k=1; k<=n; k++){
        for(i=1; i<=n; i++){
            for(j=1; j<=n; j++){
                if(i!=j && dist[i][j]>=dist[i][k]+dist[k][j])
                    dist[i][j]=dist[i][k] + dist[k][j];
            }
        }
    }

    for(i=1; i<=n; i++) dist[i][i]=0; // 자기 자신으로 가는 거리는 0으로 설정
    
    int noShare = dist[s][a] + dist[s][b], share=INF; // share : 1번 방법의 최소 비용
    						// noShare : 2번 방법의 최소 비용
    for(i=1; i<=n; i++){
        if(dist[s][i]==INF || dist[i][a]==INF || dist[i][b]==INF) continue; // 임의의 지점 i에 대해 s->i나 i->a, i->b 경로가 없으면 continue
        share = min(share, dist[s][i] + dist[i][a] + dist[i][b]); 
    }

    return noShare > share ? share : noShare;
}