[Programmers] 합승 택시 요금

A와 B가 집까지 가는 데 걸리는 최소 택시 요금을 구하는 문제이다.

중간까지 같이 가다가 중간지점에서 둘이 따로 택시를 타도 된다.

문제 해결 전략
시작점과 목표지점 두개가 주어진다.

시작점부터 중간점까지의 요금과 중간점에서 각 점까지의 요금의 합이 최소가 되는 점을 찾으면 된다.

위의 요금을 구하기 위해서는 모든 점들 사이의 요금 최솟값을 구하면 된다.

그 후 모든 점에 대하여 시작점 부터 그점, 그점부터 각 점까지의 거리의 합 중 최소가 되는 값을 구하면 된다.

우선 모든 점들 사이의 요금 최솟값을 구하기 위해 플로이드 워셜 알고리즘을 사용하였다.

플로이드 워셜
모든 점들 사이의 거리를 굉장히 큰 수로 하고 자기 자신까지의 거리일 때만 0으로 해 준다.

그리고 중간점 k에 대하여 i에서 k까지의 요금 + k에서 j까지의 요금와 i에서 j까지의 요금을 비교하여 더 작은 값을 i에서 j까지의 요금에 저장해 준다.

k를 모든 점에 대하여 실행해 준다.

요금 구하기
앞서 구한 모든 점들 간의 최소 요금을 가지고 반복문을 통해 모든 점에 대하여 확인해 준다.

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int taxi[201][201];
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i == j)
                taxi[i][j] = 0;
            else 
                taxi[i][j] = 12345678;
        }
    }
    
    for(int i=0;i<fares.size();i++){
        int aa = fares[i][0];
        int bb = fares[i][1];
        int cc = fares[i][2];
        taxi[aa][bb] = cc;
        taxi[bb][aa] = cc;
    }
    
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int tmp = taxi[i][k] + taxi[k][j];
                taxi[i][j] = min(taxi[i][j], tmp);
                taxi[j][i] = min(taxi[i][j], tmp);
            }
        }
    }
    
    int mi = taxi[s][a] + taxi[s][b];
    for(int i=1;i<=n;i++){
        if(s == i)
            continue;
        mi = min(mi, taxi[s][i] + taxi[i][a] + taxi[i][b]);
    }
    answer = mi;
    return answer;
}

출처 : 프로그래머스
https://programmers.co.kr/learn/courses/30/lessons/72413