[프로그래머스][Level3][c++][플로이드와샬] 2021 KAKAO BLIND RECRUITMENT - 합승 택시 요금 - 컴도리돌이

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

 

1.  시작 지점에서 -> 도착 지점까지의 최소 비용을 탐색해야하기 때문에 플로이드-와샬 알고리즘을 사용해야 한다.
2.  2차원 배열을 만들고 해당 값들을 큰 값으로 저장 시킨다. 여기서 주의해야할 것은 적당히 큰 수이다. 필자는 INT32_MAX를 사용해서 테스트케이스가 통과하지 못하는 현상을 겪게 되었다...
3.  2차원 배열에 경로에 따른 비용을 초기화 해주고 (n,n) 좌표들은 0으로 초기화 해준다.
4.  i -> j 로 가는 비용이랑 i -> k -> j 로 가는 비용과 비교해서 해당 i -> j 가는 비용에 최솟값을 저장시킨다.
5.  시작점(s) -> 중간 경로(i) -> A , 시작점(s) -> 중간 경로(i) -> B의 최솟값을 answer에 저장시킨다.

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

using namespace std;

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 2000000;
    vector<vector<int>> map(n+1,vector<int>(n+1,2000000));
    for(auto f : fares)map[f[0]][f[1]] = f[2], map[f[1]][f[0]] = f[2];
    
    for(int i=1; i<=n;i++) map[i][i] = 0;
    
    for(int k=1;k<=n;k++) 
        for(int i=1;i<=n;i++) 
            for(int j=1;j<=n;j++) 
                map[i][j] = min(map[i][j] , map[i][k] + map[k][j]);
    
    for(int i=1; i<=n; i++) answer = min(answer, map[s][i] + map[i][a] + map[i][b]);
    
    return answer;
}