합승 택시 요금

programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

문제의 특징은 묵시적 그래프인 것과 최단거리를 구하는 것, 합승하는 경우를 계산하는 것이다.

일반적인 최단경로 알고리즘은 다익스트라, 벨만 포드, 플로이드가 있으며, 이 문제의 경우 n이 작기 때문에 플로이드를 사용하면 n^3 = 80000으로 그렇게 오랜 시간이 걸리지 않는다.

합승하는 경우를 어떻게 판단하는지를 헷갈렸는데, 조금만 생각해보면 합승하는 경우와 합승하지 않는 경우로 답이 나뉘는걸 생각해볼 수 있다.

합승하지 않는 경우가 최솟값이라면, 플로이드로 미리 최단거리를 구해놓았기 때문에 시작지점에서 a, b까지의 거리를 바로 출력하면 된다.

합승하는 경우가 최솟값이라면, 특정 지점을 경유해서 가기 때문에 구해놓은 최단 경로들 중에서 a, b까지의 거리를 구하게 된다.

정답코드

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

using namespace std;
int dist[201][201];
#define INF 10000000
void setting(int n)
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++){
            if(i == j)
                dist[i][j] = 0;
            else
                dist[i][j] = INF;
        }
}
void floyd(int n)
{
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(dist[i][j] > dist[i][k] + dist[k][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    setting(n);
    for(const auto& fare : fares){
        dist[fare[0]][fare[1]] = fare[2];
        dist[fare[1]][fare[0]] = fare[2];
    }
    floyd(n);
    answer = dist[s][a] + dist[s][b];
    for(int i = 1; i <= n; i++)
        answer = min(dist[s][i] + dist[i][a] + dist[i][b], answer);
    return answer;
}