2021 Kakao blind 72413 - 합승 택시 요금(플로이드-와샬, 완전탐색) c++ 풀이

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

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

- 시작점이 주어져있지만, 경유지가 있기 때문에 모든 경로에 대해서 최단거리를 찾아야되기 때문에 모든 노드 쌍의 최단경로를 찾을 수 있는 플로이드 와샬 알고리즘으로 풀 수 있다. 플로이드 와샬은 한 정점에서 다른 정점을 갈 때 어떤 정점을 거쳐서 가는게 더 빠르다면 기존에 한번에 가는 정점에 거리에 더 짧은 거리값을 계속 업데이트해주는 방식이다. 

- 기본 알고리즘만 알면 쉽게 풀 수 있는 문제라고 생각된다. 이게 플로이드 문제구나라고 캐치하는게 어려운 문제이지 캐치해낸다면 금방 푸는 문제 같다. 

#include <vector>
#define INF 4000001
using namespace std;

int d[200][200];

void floyd(int n) {
    for (int k = 0; k < n; ++k) {  // 경유지 인덱스
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j)
                d[i][j] = 0;
            else
                d[i][j] = INF;
        }
    }

    for (auto& e : fares) {
        int u = e[0] - 1, v = e[1] - 1, w = e[2];
        d[u][v] = w;
        d[v][u] = w;
    }

    floyd(n);

    --s, --a, --b;
    int ans = INF;
    for (int k = 0; k < n; ++k) {
        if (ans > d[s][k] + d[k][a] + d[k][b]) {
            ans = d[s][k] + d[k][a] + d[k][b];
        }
    }

    return ans;
}