[Floyd-Warshall] (프로그래머스 Lv 3) 합승 택시 요금

문제

• 문제 링크
• 문제 설명: A, B 두 사람이 s에서 출발해서 각각의 도착 지점(a, b)까지 택시를 타고 간다고 가정할 때, 최저 예상 택시요금을 계산해서 반환하는 함수를 작성
  • 두 사람이 함께 택시를 탈 경우 비용은 1인분으로 낸다. 만약, 아예 합승을 하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승을 하지 않아도 된다.
• 입력
  • fares[i] = [c,d,f] 두 지점 c 와 d 사이의 비용 f
  • 지점갯수 n은 3 이상 200 이하인 자연수
  • 지점 s, a, b는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값
  • 즉, 출발지점, A의 도착지점, B의 도착지점은 서로 겹치지 않습니다.
  • 요금 f는 1 이상 100,000 이하인 자연수

 

 

• 출력: 최저 택시 요금

n	s	a	b	fares	result
6	4	6	2	[[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]]	82
7	3	4	1	[[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]]	14
6	4	5	6	[[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4,8], [4,3,9]]	18

풀이

• n개의 지점 중 합승 후 a와 b가 따로 갈 때 비용을 가장 적게 내는 지점을 찾아야 함
• a와 b가 s에서부터 합승해서 도착한 지점을 x 라고 할 때 cost[s][x] + cost[x][a] + cost[x][b] 가 최소가 되는 x를 찾으면 된다.
• x가 s일 경우 두 사람은 완전히 합승하지 않는 것이고 x가 a나 b일 경우 둘 중 한 명의 도착지점까지의 거리 중에 다른 한 명의 도착지점이 있는 것 (경로가 겹쳐진 것)
• 결국 모든 지점 쌍에 대해 최소 비용을 계산해야 하는데 n의 최대 크기가 200이기 때문에 플로이드-와샬로 모든 쌍에 대해 비용을 계산할 수 있음
• 주의할 점: 요금 f는 1 이상 100,000 이하인 자연수이므로 200 * 200 * 100000 = 4 * 1e9 가 되는데 중간 계산 결과가 정수형을 넘을 수 있으므로 자료형으로 long을 써야 함

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

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    long cost[n][n];
    const long INF = 1e9;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cost[i][j] = i == j ? 0 : INF; // 비용 배열 초기화
    
    for (auto& v : fares)
        cost[v[0]-1][v[1]-1] = cost[v[1]-1][v[0]-1] = v[2];
    
    // 플로이드-와샬 알고리즘
    for (int k = 0; k < n; k++) { // 매 거쳐갈(via) 지점마다 비용을 갱신
        for (int u = 0; u < n; u++) {
            if (cost[u][k] == INF) continue;
            for (int v = 0; v < n; v++)
                cost[u][v] = min(cost[u][v], cost[u][k] + cost[k][v]);
        }
    }
    
    // 최소 비용 계산
    long answer = INF;
    for (int i = 0; i < n; i++)
        answer = min(answer, cost[s-1][i] + cost[a-1][i] + cost[b-1][i]);
    return answer;
}