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

문제

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

아이디어1

플로이드 워셜

• 각 노드에서 노드 사이의 거리를 구하기

void Floyd_Warshall(vector<vector<int>>& adjMat, const int& n) {
    for(int m = 0; m < n; ++m)
    {
        for(int s = 0; s < n; ++s)
        {
            for(int e = 0; e < n; ++e)
            {
                adjMat[s][e] = min(adjMat[s][e], adjMat[s][m]+adjMat[m][e]);
            }
        }
    }
}

• $O(N^3)$
• 각 노드를 순회하며 해당 노드를 경유했을 때 가중치 비교해서 작은 값으로 덮어씌우기

아이디어2

A,B가 같이 다닌 요금 + A 요금 + B 요금 최소값 구하기

• A와 B가 갈라지기 직전까진 무조건 같이 다니는 게 최소 요금임
• A와 B가 중간에 만나는 지점이 있다고 가정하면
  • 그러면 해당 지점까지 A와 B 요금은 같아야함
  • 서로 다른 길로 왔다면 같이 오는 것 보다 요금이 더 들어감

int two_sum_fare(int n, int s, int a, int b, const vector<vector<int>>& adjMat)
{
    int fare = LARGE_NUM;
    for (int i = 0; i < n; ++i)
    {
        fare = min(fare, adjMat[s][i] + adjMat[i][a] + adjMat[i][b]);
    }
    
    return fare;
}

주의할 점

INF 값을 오류가 생기지 않을 최대한 큰 값으로 설정

예) #define LARGE_NUM 0x0FFFFFFF

더 효율 좋은 방법

• 플로이드 워셜 방법은 전부 순회해서 각 노드 사이에 거리를 구함
• a,b가 갈라지는 중간 지점을 m이라 하면
  • "s->m" + "m->a" + "m->b"의 요금이 최소가 되면 됨
  • 이 값은
    "m->s" + "m->a" + "m->b" 또는
    "s->m" + "a->m" + "b->m" 과 같음
• 즉, 다익스트라를 이용해 s, a, b를 시작 노드로 최소 거리들을 구한 후
  • (s->m, a->m, b->m 들을 구한 것과 같음)
• 노드를 순회해 해당 노드부터 s, a, b까지의 거리의 합이 최소가 되는 값을 구하면 됨
  • (m->s, m->a, m->b의 합이 최소가 되는 값을 구하는 것임)