[카카오] 합승택시요금

문제 요약

1. S에 어피치와 무지가 있습니다. 어피치의집은 A, 무지의 집은 B입니다.
   이 둘은 항상 집에 갈 때 택시만 타는데(걷는 일 없음), 택시요금을 아끼기 위해 합승을 하려 하는데 가장 저렴한 경우의 가격을 반환하세요.
2. 어떤 지점 ?번까지만 택시 한 대에 동승하고, 찢어져 갈 수 있습니다.
3. S에서 각자 택시를 타고 가는 것이 더 저렴할 수도 있습니다.

반년전엔..

카카오 코딩테스트에서 이 문제를 만났었다. 당시에도 플로이드 워셜 알고리즘의 존재를 알았지만 N:N shortest path를 O(N^3) 걸려 구하고 ?번을 바꿔가며 구한다는 게 마음에 안들어서 다익스트라로 접근하다가 풀기를 포기했던 문제이다. 하지만 플로이드 워셜의 O(N^3)은 상당히 빠르다.

아이디어

N:N shortest path를 플로이드워셜 알고리즘으로 O(N^3) 걸려 구하고 ?번을 바꿔가며 O(N)걸려서 구한다

?번에 들어갈 수 있는 번호

S, A, B를 포함한 1번~N번이 그 대상이다.

코드

25분컷

#include <string>
#include <vector>
#include<iostream>
#include<math.h>
using namespace std;
int INF = 200*100000;
int tab[201][201];

void floyd(int n, vector<vector<int>> fares){
    //배열 초기화
    for(int i = 1;i<=n;i++){
        for(int j =1;j<=n;j++){
            tab[i][j] = INF;
            if(i == j) tab[i][j] = 0;
        }
    }
    //간선 반영
    for(int ctr = 0;ctr<fares.size();ctr++){
        int c = fares[ctr][0],d = fares[ctr][1],f = fares[ctr][2];
        tab[c][d] = f;
        tab[d][c] = f;
    }

    for(int k = 1;k<=n;k++){
        for(int i = 1;i<=n;i++){
            for(int j =1;j<=n;j++){
                if(tab[i][k]+tab[k][j]<tab[i][j]){
                    tab[i][j] = tab[i][k]+tab[k][j];
                }
            }
        }
    }
}


int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    floyd(n,fares);
    int mind = INF*3;
    for(int k = 1;k<=n;k++){
        int d = tab[s][k]+tab[k][a]+tab[k][b];
        mind = min(mind,d);
    }
    answer = mind;
    return answer;
}