[프로그래머스] 합승 택시 요금 - Dijkstra 풀이 복기

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

프로그래머스

 

오늘은 합승 택시 요금 문제를 풀어보았다.

이 문제는 출발지에서 A와 B가 같이 택시를 타서 각자의 목적지까지 가는 최소 요금을 구하는 문제이다. 중간에 내려서 따로 택시를 타고 가는 방법도 가능하다.

 

단순히 A에서 B까지 최단 거리를 구하는 문제가 아니어서 꽤나 어려웠다.

그리고 코드가 돌아가기만 하면 되는 게 아니라 효율성까지 봐서 한 번 더 생각해야 했다.

 

나는 총 3번의 접근을 시도한 끝에 풀 수 있었고, 각 과정에서 필요했던 포인트들을 정리했다.

 

(여기서 자세한 다익스트라 알고리즘의 원리는 소개하지 않는다.

다익스트라를 사용했지만 정확도, 효율성에서 문제를 겪은 분들이 보시면 좋을 것 같다.)

 

1. [반례] A-B 최단 경로가 최적이 아닐 수 있다.

 

마침 컴퓨터 네트워크 전공 수업에서 다익스트라 알고리즘을 배웠기에, 사용할 알고리즘은 비교적 쉽게 찾아냈다.

하지만, A-B 사이의 최단 경로가 최종 경로에 무조건 포함될 것이라고 생각한 게 실수였다.

분기점이 A-B 최단 경로 위에서 나오지 않는 경우도 있었기 때문이다. 그림으로 보면 다음과 같다.

      10
A -------- B
 \        /
  \6    6/
   \    /
     K
     |
     |1
     |
     S

 

(예시 코드 목록에 없어서 전혀 몰랐다...)

그렇기 때문에, 특정 노드 K로부터 S, A, B까지의 최단 경로의 합 중에서, 최솟값을 찾는 것이 올바른 접근 방법이었다.

이런 식으로.

min(dist[k][s] + dist[k][a] + dist[k][b])

 

 

Q. 근데 이 반례는 대체 어떻게 생각해낼 수 있는 걸까?

-> 내가 가정한 풀이가 어떤 경우를 배제하고 있는지 의식적으로 상황을 만들어본다.

 

나같은 경우, A와 B의 최단 경로 위에서 분기점이 있다고 가정했으므로,

다른 곳에서 분기점이 있는 경우를 그려보는 것이다.

 

2. [디폴트값] INF는 (한 간선의 최대 cost * 간선 개수)보다 커야한다.

 

나는 INF를 (한 간선의 최댓값 + 1)인 100,001로 정의했었는데, 그러면 다익스트라의 핵심 로직인 최소 비용을 비교하는 로직에서 오류가 발생할 수 있다.

따라서 INF는 충분히 큰 값으로 선언해야 한다.

// cur: 현재 탐색 중인 노드
// adj: 현재 탐색 중인 cur 노드와 인접한 노드
// D[w]: 시작 노드부터 w 노드까지의 최단 경로 cost
// c[a][b]: 인접한 a, b 노드 사이의 cost

// 기존의 adj로 가는 비용보다 cur를 거쳐서 가는 비용이 더 적으면 update  
D[adj] = min(D[adj], D[cur] + c[cur][adj]); // 100001 < ( 100000 + 100000 ) !!

 

 

3. [시간 복잡도] 모든 노드에 대해 다익스트라를 돌리지 않아도 된다.

 

모든 노드에 대해 다익스트라를 돌리고 minCost를 업데이트하면 모든 문항이 시간 초과가 뜨는 경험을 할 것이다.

위의 방법은 O(N^3)의 시간 복잡도를 가진다. (다익스트라에서 N^2, 모든 노드에 대하여 돌리므로 *N해서 N^3)

 

하지만, O(N^2)만으로 풀 수 있는 방법이 있다.

바로 S, A, B에 대해서만 다익스트라를 돌리는 것이다.

각각의 결과를 distS, distA, distB에 저장해둔 뒤, 세 노드로부터 분기점 K 노드까지의 최단 경로의 합 중 가장 작은 비용이 정답이다.

for K in all nodes
	minCost = min(minCost, distS[K] + distA[K] + distB[K])

 

 

4. 전체 코드

AI로 피드백을 받은 결과, 처음에는 최단 경로를 찾은 노드들을 N_ 전역 변수에  담아두고, 이를 탐색에서 제외하기 위해 find 연산을 사용했으나 이는 순회 비용이 많이 든다고 한다.

그래서 bool visited 로 바꾸었더니 전역 변수를 쓰지 않아도 되고 코드도 깔끔해졌다.

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 20000000

using namespace std;

vector<int> N;
vector<vector<int>> c;

vector<int> dijkstra(int n, int start) {
    vector<int> D(n + 1, INF);
    vector<bool> visited(n + 1, false);

    // 시작 노드까지의 거리
    D[start] = 0;

    // 모든 노드의 최단 경로가 확정될 때까지 loop
    while (true) {
        int nextNode = -1;
        int minCost = INF;

        // 확정되지 않은 노드들 중 가장 작은 cost를 가진 노드 찾기
        for (int node : N) {
            if (visited[node] == false) {
                if (D[node] < minCost) {
                    minCost = D[node];
                    nextNode = node; // 다음에 순회할 노드인 nextNode로 확정
                }
            }
        }

        if (nextNode == -1) break;
        visited[nextNode] = true;

        // nextNode와 인접한 노드의 최단 경로 update
        for (int adjacentNode : N) {
            if (visited[adjacentNode] == false) {
                if (c[nextNode][adjacentNode] != INF) {
                    int newCost = D[nextNode] + c[nextNode][adjacentNode];

                    if (newCost < D[adjacentNode]) {
                        D[adjacentNode] = newCost;
                    }
                }
            }
        }
    }

    return D;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    c.assign(n + 1, vector<int>(n + 1, INF));

    for (int i = 1; i <= n; i++) {
        N.push_back(i);
    }

    for (int i = 0; i < fares.size(); i++) {
        int from = fares[i][0];
        int to = fares[i][1];
        int cost = fares[i][2];

        c[from][to] = cost;
        c[to][from] = cost;
    }

    vector<int> distS = dijkstra(n, s);
    vector<int> distA = dijkstra(n, a);
    vector<int> distB = dijkstra(n, b);

    int minCost = INF;

    for (int k : N) {
        minCost = min(minCost, distS[k] + distA[k] + distB[k]);
    }

    int answer = minCost;

    return answer;
}