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

코딩테스트 연습 - 합승 택시 요금 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

처음엔 다익스트라로 각각의 최단 경로를 구한 이후 각 노드의 이전 노드를 저장한 후 겹치는 부분에 대해서 한 번만 더하는 식으로 진행하려고 했는데 다익스트라를 구현하고 각각 a, b까지의 최단 경로를 출력해보니 아예 다른 값이 나와서 급하게 노선을 틀었다.

그러다 특정 노드에서 a,b로의 최단 경로와 s에서 부터 특정 노드까지의 거리의 합을 구하면 끝나곘다 생각이 들었고 플로이드 워셜 알고리즘을 통해 노드와 노드사이의 최단 경로를 구해준 후 모든 특정 노드에 대해 최솟값을 찾아주었다.

 

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int val[201][201];

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 987654321;
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=n; j++){
            if(i!=j)
                val[i][j]=987654321;
        }
    }
    for (int i=0; i<fares.size(); i++) {
        val[fares[i][0]][fares[i][1]]=fares[i][2];
        val[fares[i][1]][fares[i][0]]=fares[i][2];
    }
    for(int k=1; k<=n; k++){
        for(int i = 1; i<=n; i++){
            for(int j=1;j<=n;j++){
                val[i][j]=min(val[i][j], val[i][k]+val[k][j]);
            }
        }
    }
    
    for(int i = 1; i<=n; i++){
        if(val[i][a]==987654321|| val[i][b]==987654321||val[s][i]==987654321) continue;
        answer=min(answer, val[i][a]+val[i][b]+val[s][i]);
    }
    return answer;
}