프로그래머스 - 합승 택시 요금 - C++

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    
    vector<vector<int>> dist(n+1,vector<int>(n+1,1e8));
    for (auto& item : fares)
    {
        dist[item[0]][item[1]] = item[2];
        dist[item[1]][item[0]] = item[2];
    }
    
    for(int i=1;i<=n;i++)dist[i][i]=0;
    
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dist[i][j]>dist[i][k]+dist[k][j])
                    dist[i][j]=dist[i][k]+dist[k][j];
    
    // 각자 타고 갈때 비용을 초기값으로
    answer=dist[s][a]+dist[s][b];
    
    for(int k=1;k<=n;k++)
    {
        if(dist[s][k]+dist[k][a]+dist[k][b]<answer)
            answer=dist[s][k]+dist[k][a]+dist[k][b];
    }
    
    return answer;
}

문제는 두 사람이 타고가는 택시 비용의 합을 최소로 줄이는 것에 있다. 

따라서 각각의 경로에 대한 최소비용을 알고 있어야한다.

그래서 플로이드-워샬 알고리즘을 이용해 먼저 각 경로에 대한 최소비용을 구한다.

그 후, answer를 각자가 따로 집으로 갈때 비용으로 초기화한다.

 

그 후, 두 사람이 택시를 타고 k 지점까지 간 후, 따로 집에 갈때의 비용을 계산해 그 값이 현재 최소값보다 작다면 갱신하는 방식으로 찾으면 된다. 

 

vector<vector<int>> dist(n+1,vector<int>(n+1,1e8));
    for (auto& item : fares)
    {
        dist[item[0]][item[1]] = item[2];
        dist[item[1]][item[0]] = item[2];
    }
    
    for(int i=1;i<=n;i++)dist[i][i]=0;

graph를 만드는 과정이다. 무방향그래프이기 때문에 양 방향을 전부 추가해줘야한다. 

 

for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dist[i][j]>dist[i][k]+dist[k][j])
                    dist[i][j]=dist[i][k]+dist[k][j];

플로이드-워샬 알고리즘이다. 

 

// 각자 타고 갈때 비용을 초기값으로
    answer=dist[s][a]+dist[s][b];
    
    for(int k=1;k<=n;k++)
    {
        if(dist[s][k]+dist[k][a]+dist[k][b]<answer)
            answer=dist[s][k]+dist[k][a]+dist[k][b];
    }

answer를 초기값으로 설정해주고 

둘이 k지점까지 간 후, 각자 타고 갔을 때 비용이 더 싸다면 갱신해준다.