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

programmers.co.kr/learn/courses/30/lessons/72413

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

<풀이>

1. 적절한 지점까지 합승을 하여, 택시 요금이 최소가 되는 택시 요금을 구한다.

2. 최소 택시 요금을 반환한다.

 

<해법>

택시 합승은 다음과 같이 이루어집니다.

s에서 어떤 지점까지는 합승을 하고, 그 지점에서 각자 택시를 타고 가는 것입니다.

이 때 알아야 하는 것은 s에서 어떤 지점까지 가는 최소 요금, 어떤 지점에서 각자 도착지점까지 가는 최소 요금 이렇게 두 가지 입니다.

여기서 모든 정점 간의 최소거리를 계산하는 플로이드 알고리즘을 떠올릴 수 있습니다. 

따라서, 플로이드 알고리즘을 이용하여 모든 정점 간의 최소 거리를 구하고, 각각 지점까지 합승했을 때의 택시요금을 구한 후, 그 중 최소요금을 반환합니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <string.h>
#include <algorithm>
#define INF 123456789
 
using namespace std;
 
int W[201][201]; //주어진 그래프
int D[201][201]; //플로이드 알고리즘을 거친 후, 최단거리 배열
 
//플로이드 알고리즘
void floyd(int n) {
 
    //초기화
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            D[i][j] = W[i][j];
        }
    }
 
    //플로이드 핵심
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
            }
        }
    }
    
}
 
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
 
    int answer = INF;
 
    //초기화
    memset(W, INF, sizeof(W));
    for (int i = 1; i <= n; i++) {
        //1번지점 -> 1번지점으로 가는 경우 -> 0원
        W[i][i] = 0;
    }
 
    //그래프 그리기
    for (int i = 0; i < fares.size(); i++) {
        int first = fares[i][0];
        int second = fares[i][1];
        int fare = fares[i][2];
 
        W[first][second] = fare;
        W[second][first] = fare;
    }
 
    //플로이드 알고리즘
    floyd(n);
 
    //정답 갱신
    for (int i = 1; i <= n; i++) {
        /*
        D[s][i] + D[i][a] + D[i][b]
        : s부터 i까지는 같이가고, i부터는 각자 가는 경우의 택시요금
        */
        answer = min(answer, D[s][i] + D[i][a] + D[i][b]);
    }
 
    //반환
    return answer;
}

 

플로이드 알고리즘에 대해 알아볼 수 있는 문제였습니다.