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

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

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

 이 문제는 무지와 어피치가 어디까지 합승을 해야 가장 요금이 적게 나오는지를 구하는 문제이다. 그리고 이는 플로이드 와샬 알고리즘을 이용해 풀 수 있는 문제이다. 왜냐하면, 이 문제를 풀기 위해서는 각 노드에서 각 노드까지의 최단 거리(이 문제에서는 최소 요금)을 알아야 하는데, 플로이드 와샬 알고리즘을 이용하면 모든 노드에서 모든 노드까지의 최단 거리, 혹은 최소 요금을 계산할 수 있기 때문이다. 이 알고리즘을 이용해 각 노드 사이의 모든 최소 거리를 구한 후, 모든 경우의 최소 요금을 비교하면 된다. 이 문제를 풀기 위해 구상한 절차는 다음과 같다.

1. 우선 요금을 저장할 변수(costs라는 이름의 2차원 배열)을 초기화한다. 이 때 , 출발 노드와 도착 노드가 같다면 0을, 다르다면 INF(가능한 엄청 큰 값)로 값을 설정한다.
2. 주어진 fares 정보를 1번의 costs에 저장한다.
3. 플로이드 와샬 알고리즘을 이용해 모든 경우의 최소 요금을 구한다.
4. 시작지점 -> 무치 도착 지점 -> 어피치 도착 지점의 최소 요금과 시작 지점 -> 어피치 도착 지점 -> 무지 도착 지점의 최소 요금을 비교해 더 작은 값을 저장한다.(answer라는 이름의 변수). 이는  합승 안 하는 경우도 존재할 수 있기 때문이다. (예제 2번)
5. 1번 노드부터 n번 노드를 반복하면서, 각 노드까지 합승하였을 경우의 요금과 answer의 값을 비교한 후, 더 작은 값을 answer에 저장한다. (mid까지 합승한다고 할 때, 요금은 dist[시작지점][mid] + dist[mid][무치_도착_지점] + dist[mid][어피치_도착_지점]이 된다.)

#include <string>
#include <vector>
#include <memory.h>
using namespace std;

#define MAX 201
#define INF 5000000 // 이 값을 꽤 크게 주는 게 중요하다고 생각한다

int costs[MAX][MAX];

int solution(int n, int s, int a, int b, vector<vector<int>> fares) 
{
    for (int from = 1; from <= n; ++from)
    {
        for (int to = 1; to <= n; ++to)
        {
            if (from == to)
                costs[from][to] = 0;
            else
                costs[from][to] = INF;
        }
    }

    for (int i = 0; i < fares.size(); ++i)
    {
        vector<int> fare = fares[i];

        int nodeA = fare[0];
        int nodeB = fare[1];
        int cost = fare[2];

        costs[nodeA][nodeB] = cost;
        costs[nodeB][nodeA] = cost;
    }
    
    for (int mid = 1; mid <= n; ++mid)
    {
        for (int start = 1; start <= n; ++start)
        {
            for (int end = 1; end <= n; ++end)
            {
                if (costs[start][end] > costs[start][mid] + costs[mid][end])
                    costs[start][end] = costs[start][mid] + costs[mid][end];
            }
        }
    }
    
    int answer = min(costs[s][a] + costs[a][b], costs[s][b] + costs[b][a]);

    for (int mid = 1; mid <= n; ++mid)
        answer = min(answer, costs[s][mid] + costs[mid][a] + costs[mid][b]);
    
    return answer;
}