[Graph] 합승 택시 요금 - 2021 KAKAO BLIND RECRUITMENT

해결 방법

처음엔 BFS+DP로 시도해보았는데 시간초과가 나서 결국은 플로이드 와샬(Floyd Warshall) 알고리즘으로 해결했다.

플로이드 와샬 알고리즘은 각 정점끼리의 모든 최단 경로를 구해야할 때 사용되는 알고리즘이며, 구현하기 매우 쉽다는 장점이 있다.

자세한 동작을 알고싶다면 나동빈님의 블로그를 참고하길 바란다.

https://blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

 

소스 코드

#include <string>
#include <vector>
using namespace std;

int min_fare[201][201];
int maxi=20000001;

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) min_fare[i][j]=maxi;
    for(int i=1;i<=n;i++) min_fare[i][i]=0;
    for(int i=0;i<fares.size();i++){
        min_fare[fares[i][0]][fares[i][1]]=fares[i][2];
        min_fare[fares[i][1]][fares[i][0]]=fares[i][2];
    }
    for(int p=1;p<=n;p++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                min_fare[i][j] = min(min_fare[i][j], min_fare[i][p]+min_fare[p][j]);
            }
        }
    }
    int answer = maxi;
    for(int i=1;i<=n;i++) answer=min(answer, min_fare[s][i]+min_fare[i][a]+min_fare[i][b]);
    return answer;
}

 

정확성, 효율성 모두 만점

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/72413