[Algorithm] 프로그래머스 합승 택시 요금 - C++, 플로이드 와샬

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

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

const int MAX = 999999999;
long long costs[201][201];
using namespace std;

void MakePath(int n){
    for(int via = 1; via <= n; via++){
        for(int from = 1; from <= n; from++){
            for(int to = 1; to <= n; to++){
                if(costs[from][to] > costs[from][via] + costs[via][to]){
                    costs[from][to] = costs[from][via] + costs[via][to];
                }
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = MAX;

    // init cost array
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            if(i == j)  continue;
            costs[i][j] = MAX;
        }  
    }
        

    // make edges array
    for(int i = 0; i < fares.size(); i++){
        int posA = fares[i][0];
        int posB = fares[i][1];
        int cost = fares[i][2];

        costs[posA][posB] = cost;
        costs[posB][posA] = cost;
    }

    // find all route
    MakePath(n);

    // find min cost
    for(int i = 1; i <= n; i++){
        long long curCost = costs[s][i] + costs[i][a] + costs[i][b];
        if(curCost < answer)
            answer = curCost;
    }

    return answer;
}

---

 solution 함수에서 주어지는 fares 벡터를 플로이드 와샬용 costs 2차원 배열로 변경한 뒤 for문으로 n 만큼 돌면서 환승 지역 경우의 수를 모두 보는 방법으로 풀이를 했습니다.

 다익스트라에 배열 초기화 코드를 넣어둔 뒤 다익스트라를 n 번 하는 것으로 풀어도 괜찮아 보였습니다만 n 이 크지 않아서 코드가 간단한 플로이드 와샬로 풀이를 했습니다.