[Programmers] 합승 택시 요금

안녕하세요. 오늘은 Programmers 합승 택시 요금을 풀어보도록 하겠습니다.

 

해당 문제는 

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

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

 

위 링크에서 확인하실 수 있습니다.

 

진짜 맨날 문자열, 구현에 고통 많이 받았는데 그나마 숨이 좀 트이는 문제입니다.

문제의 n제한이 200까지이기 때문에 통상적으로 n^3의 알고리즘을 쓰더라도 큰 문제가 없습니다.

그리고 그래프에 가중치가 있고, 음의 가중치가 없기 때문에

 

다익스트라 or 플로이드 와샬 둘 중 하나를 쓰는 문제이겠거니 짐작하고 들어가시면 좋습니다.

 

결론적으로 이 문제는 플로이드 와샬로 해결하였는데, 

 

시작 지점이 s라고 하고 환승이 끝나는 지점을 x라고 해보면, 

 

s -> x (공통)

x -> a 

x -> b

 

이 세 값을 더한 결과가 최소가 되는 x를 찾으면 됩니다. 플로이드 와샬 알고리즘을 사용하게 되면 모든 정점부터 모든 정점까지 거리의 최솟값을 구할 수 있습니다. 따라서 미리 모든 정점부터 정점까지의 최단거리를 구해놓은 다음에

위 식의 결과가 최소가 되는 x값만 마지막에 구해주시면 됩니다.

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;

int d[204][204];
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 10000004;
    fill(&d[0][0], &d[0][0]+204*204, 10000004);
    for(int i = 0; i < fares.size(); i++) {
        d[fares[i][0]][fares[i][1]] = fares[i][2];
        d[fares[i][1]][fares[i][0]] = fares[i][2];
    }
    for(int i = 1; i <= n; i++)
        d[i][i] = 0;
    
    // floydWarshall
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) 
                if(d[i][k]+d[k][j] < d[i][j]) d[i][j] = d[i][k]+d[k][j];
        }
    }
    
    for(int i = 1; i <= n; i++) {
        int fare = d[s][i] + d[i][a] + d[i][b];
        answer = min(answer, fare);       
    }
    
    return answer;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.