[C++] 프로그래머스 합승 택시 요금

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

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

이 문제는 딱 보자마자 플로이드-와샬 알고리즘으로 쉽게 풀 수 있는 문제임을 직감했다. 모든 정점에서 다른 모든 정점으로의 최단 경로를 구한 다음 시작정점으로부터 한 지점을 거쳐서 각각 A, B의 집을 가는 경로의 최솟값을 구하면 된다. 코드는 다음과 같다.

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

using namespace std;

const int MN = 201;
const int INF = 1e9; //무한대

int floyd[MN][MN]; //최단 경로를 저장할 배열

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    fill(&floyd[0][0], &floyd[n][n+1], INF); //최단 경로 무한대로 초기화
    for(int i = 1; i <= n; i++)
        floyd[i][i] = 0; //자기 자신은 0으로 초기화
    
    for(vector<int> e : fares) { //u->v와 v->u 모두 가능하므로 양방향으로 초기화
        floyd[e[0]][e[1]] = e[2];
        floyd[e[1]][e[0]] = e[2];
    }
    for(int k = 1; k <= n; k++) { //플로이드-와샬 알고리즘 수행 k정점을 통해 갔을 경우를 각각 계산
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j]);
            }
        }
    }
    
    for(int k = 1; k <= n; k++) { //1번 정점부터 n번 정점까지 출발점부터 k를 지나 a, b로 각각 가는 합 계산
        int tmp = floyd[s][k] + floyd[k][a] + floyd[k][b];
        if(tmp < 0) continue; //오버플로우 방지
        answer = min(answer, tmp); //최솟값 갱신
    }
    
    return answer;
}

    초기화를 1e9인 10억으로 했기 때문에 만약 s->k, k->a, k->b 경로가 모두 없는 경우 30억으로 약 21억인 정수형 범위를 넘어가게 된다. 그렇기 때문에 오버플로우 방지로 계산한 결과 값이 0보다 큰 경우에만 최소값을 갱신해야한다. 그렇지 않으면 엄청나게 작은 수가 최소값으로 갱신될 것이다.

 

    플로이드-와샬 알고리즘을 수행하는 부분은 가운데에 있는 3중 반복문이다. k정점을 지나는 경우를 계속 최단 경로로 갱신하여 모든 정점에서 다른 모든 정점으로의 최단 경로를 구할 수 있다. 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 다익스트라나 벨만-포드 알고리즘은 O(n^2)의 알고리즘이 가능하지만 모든 정점에서의 최단 경로를 모두 구하는 플로이드-와샬 알고리즘은 O(n^3)의 알고리즘이 최선이다. 문제의 조건에 따라 다익스트라를 사용할지 플로이드-와샬 알고리즘을 사용할지 잘 판단해야한다.