(C++) - 프로그래머스(2021 KAKAO BLIND RECRUITMENT) : 합승 택시 요금

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

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

Floyd Warshell문제였습니다

 

풀이방법

 1. 요금정보를 저장할 배열 charge를 큰 값(INF)로 초기화해줍니다. 이 후 자기 자신으로 가는 요금정보는 없기 때문에 i -> i로 가는 비용은 0으로 초기화해줍니다. 

 

 2. 주어진 요금정보를 인접 그래프의 형태로 바꿔줍니다. fare[i][0] -> fare[i][1]로 가는 요금이 fare[i][2]입니다. 양방향 그래프이므로 fare[i][1] -> fare[i][0]으로 가는 요금도 fare[i][2]로 같습니다.

 

 3. floyd warshell을 이용해 모든 정점사이의 최소거리를 구해줍니다. i -> k 로 가는 비용 + k -> j로 가는 비용이 i -> j로 가는 비용보다 저렴하다면 charge배열을 갱신해주는 방식으로 O(N^3)의 시간복잡도를 가집니다.

 

 4. ans를 구해줍니다. ans의 처음값은 동승하지않고 각자 도착지점으로 택시를 탔을 때 비용들의 합입니다. 즉, charge[s][a] + charge[s][b]입니다. 이 후 적절히 합승했을 때 전체 비용을 다음과 같이 구합니다.

 s -> i까지 합승합니다. 그 후 i지점에서 각자 a와 b지점으로 갑니다. 이는 charge[s][i] + charge[i][a] + charge[i][b]로 표현될 수 있습니다. 이 값이 ans보다 작다면 ans를 갱신해줍니다.

 

 5. ans를 반환합니다.

 

 

Code

#include <bits/stdc++.h>
#define INF 1000000000
#define ll long long
using namespace std;
ll charge[201][201], N, ans;

void initCharge(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            charge[i][j] = INF;
        }
    }
}

void makeChargeMatrix(vector<vector<int>> fares){
    for(int i = 0; i < fares.size(); i++){
        charge[fares[i][0]][fares[i][1]] = fares[i][2];
        charge[fares[i][1]][fares[i][0]] = fares[i][2];
    }
    for(int i = 1; i <= N; i++) charge[i][i] = 0;
}

void makeFloyd(){
    for(int k = 1; k <= N; k++){
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                if(i == j || j == k || i == k) continue;
                charge[i][j] = min(charge[i][j],charge[i][k] + charge[k][j]);
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    N = n;
    initCharge();
    makeChargeMatrix(fares);
    makeFloyd();
    ans = charge[s][a] + charge[s][b];

    for(int i = 1; i <= N; i++){
        //n까지 동승해서 흩어지는 것이 기존 따로 가는 것보다 작다면
        ans = min(ans,charge[s][i] + charge[i][a] + charge[i][b]);
    }

    return (int)ans;
}