[프로그래머스 Lv3] : 합승 택시 요금

문제 링크

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

프로그래머스

무지와 어피치가 각자의 목적지로 가기 위해 택시를 이용할 때, 최소 이용 요금을 리턴해주자.

합승은 해도되고 안해도 된다.

 

풀이

 비용이 최소가 되도록 각자의 목적지에 도달해야 하기 때문에 "최단거리" 알고리즘을 사용해야한다는 것을 알 수 있다. 그런데 무지와 어피치가 어디까지 합승을 하는 것이 비용적인 면에서 가장 효율적으로 이동할 수 있는지, 바로 파악하기가 어렵다.

무지의 도착점을 A, 어피치의 도착점을 B라고 했을 때 합승해서 가는 중간지점을 C라고 하자.

이들의 경로를 모두 모아보면, 시작점 -> C ( 합승 ), C -> A ( 무지 ), C -> B ( 어피치 ) 이렇게 세 구간이 있다.

세 구간을 이동하는 비용의 합이 최소가 되도록 하면 된다.

만약 시작점과 C가 일치한다면 합승을 하지 않는 것이라 생각해도 된다.

 

 최단거리 알고리즘 중에서 "플로이드-와샬" 알고리즘을 이용하는게 가장 적합하다.

플로이드 와샬 알고리즘은 모든 정점 사이의 최단 거리를 구할 수 있기 때문이다.

 

 예전에 이 알고리즘을 접했을 때 이해하기가 어려워서 포기했었는데, 이번에 이 문제를 풀기위해 다시 읽어봤다.

알고리즘은 생각보다 간단했다.

임의의 정점 k를 경유지로 설정해서 두 정점 사이의 거리를 갱신하는 원리다.

정점 i 와 j 사이의 거리를  Dist[ i ][ j ] 라고 하자.

모든 경유지(정점) k에 대해서

기존의 Dist[ i ][ j ] 와 k를 경유해서 가는 Dist[ i ][ k ] + Dist[ k ][ j ] 두 값을 비교해서 Dist[ i ][ j ] 값을 갱신해주는 방식이다.

 

플로이드 와샬 알고리즘만 코드로 나타내면 다음과 같다. 

n개의 정점에 대해서

for(int k = 1; k <= n; k++){ //경유지 k
	for(int i = 1; i <= n; i++){ //임의의 정점 i
    		for(int j = 1; j <= n; j++){ //임의의 정점 j
        		Dist[i][j] = min(Dist[i][j], Dist[i][k] + Dist[k][j]);
        	}
	}
}

 

모든 정점 사이의 최단거리를 구한 후,

합승해서 가는 중간지점 C를 모든 정점에 대해 가능성을 열어두고

Dist[ s ][ c ] + Dist[ c ][ a ] + Dist[ c ][ b ] 값 중 최소가 되는 값을 찾으면 된다.

 

코드 작성

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200 + 5;
const int INF = INT_MAX;
int Dist[MAX_N][MAX_N];
 
void Init(){
    for(int i = 0;i <MAX_N; i++)
        for(int j = 0; j<MAX_N;j++){
            if(i == j)
                Dist[i][j] = 0;
            else Dist[i][j] = INF;
        }
}
 
void Floyd(int n){
    for(int i = 1; i<=n; i++) //경유지
        for(int j = 1; j<=n; j++)
            for(int k = 1; k<=n; k++){
                if(Dist[j][i] == INF || Dist[i][k] == INF)
                    continue;
                Dist[j][k] = min(Dist[j][k], Dist[j][i] + Dist[i][k]);
            }
}
 
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    Init();
    for(auto v : fares){
        int from = v[0];
        int to = v[1];
        int weight = v[2];
        Dist[from][to] = Dist[to][from] = weight;
    }
    Floyd(n);
    for(int i = 1; i<=n; i++){
        answer = min(answer, Dist[s][i] + Dist[i][a] + Dist[i][b]);
        //i까지 합승 + A따로 + B따로
    }
    return answer;
}

 

예전에 이 알고리즘을 처음 접했을 때, 이해가 안 돼서 이해하기를 포기했었다.

다시 보니까 생각보다 어렵지 않아서, 이 정도를 이해하기 포기했던 과거의 나를 반성하게 됐다.