기차 요금표에서 목적지까지 최소 비용 경로 찾기 (동적 계획법)

여행 경로에 N개의 정거장이 있고, 열차는 0번 정거장에서 출발하여 N-1번 정거장(목적지)에 도착한다고 가정해 봅시다. 모든 정거장 쌍 사이의 티켓 요금이 표(행렬) 형태로 주어졌을 때, 주어진 요금만을 사용하여 목적지에 도달하는 최소 비용을 구하는 것이 이 문제의 목표입니다.

이 문제는 각 정거장까지 도달하는 최소 비용을 순차적으로 갱신해 나가는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다.

입력 및 출력

입력: 여행 경로의 비용 행렬
0  15  80  90
∞   0   40  50
∞   ∞   0   70
∞   ∞   ∞   0

출력:
최소 비용은 65입니다.
먼저 0번에서 1번 정거장으로 이동하고(비용 15),
이후 1번에서 3번 정거장으로 이동합니다(비용 50).
따라서 총 비용은 65입니다.

알고리즘

findMinCost(cost)

입력 − 각 출발지에서 각 목적지까지의 비용이 담긴 행렬

출력 − 목적지에 도달하기 위한 최소 비용

핵심 아이디어는 다음과 같습니다. 각 정거장 j까지의 최소 비용은, 그 앞의 어떤 정거장 i를 거쳐 오는 경우와 직접 비교하여 더 작은 값으로 계속 갱신하는 것입니다.

Begin
    정거장 수와 같은 크기의 배열 costLoc을 정의하고,
    모든 값을 ∞(무한대)로 초기화한다.
    n := 정거장의 개수
    costLoc[0] := 0   // 출발지의 비용은 0

    각 출발지 i에서 각 목적지 j에 대해 반복:
        만약 costLoc[j] > costLoc[i] + cost[i, j] 라면
            costLoc[j] := costLoc[i] + cost[i, j] 으로 갱신
    done

    return costLoc[n-1]   // 마지막 정거장까지의 최소 비용 반환
End

C++ 구현 예제

#include<iostream>
#define INF INT_MAX
#define NODE 4
using namespace std;

int cost[NODE][NODE] = {
    {0, 15, 80, 90},
    {INF, 0, 40, 50},
    {INF, INF, 0, 70},
    {INF, INF, INF, 0}
};

int findMinCost() {          // 목적지에 도달하는 최소 비용 계산
    int costStation[NODE];   // 0번 역에서 각 역까지의 비용 저장

    for (int i = 0; i < NODE; i++)
        costStation[i] = INF;        // 처음에는 모두 무한대로 초기화
    costStation[0] = 0;              // 출발점인 0번 역의 비용은 0

    for (int i = 0; i < NODE; i++)
        for (int j = i + 1; j < NODE; j++)
            if (costStation[j] > costStation[i] + cost[i][j]) // 더 저렴한 경로 발견 시
                costStation[j] = costStation[i] + cost[i][j]; // 중간 경유 역을 통한 최소 비용으로 갱신
    return costStation[NODE - 1];
}

int main() {
    cout << "정거장 " << NODE << "번에 도달하는 최소 비용은 " << findMinCost() << endl;
    return 0;
}

실행 결과

정거장 4번에 도달하는 최소 비용은 65

동작 원리 설명

위 코드에서 0번 정거장에서 출발할 때의 선택지를 살펴보면 다음과 같습니다.

• 직접 이동: 0 → 3번 정거장, 비용 90
• 1번 경유: 0 → 1(15) → 3(50), 총 비용 65
• 2번 경유: 0 → 1(15) → 2(40) → 3(70), 총 비용 125

세 가지 경로 중 1번 정거장을 경유하는 경로의 비용 65가 가장 작으므로, 알고리즘은 이 값을 최종 결과로 반환합니다.

이 알고리즘의 시간 복잡도는 이중 반복문을 사용하므로 O(N²)이며, 추가 배열 하나만 사용하므로 공간 복잡도는 O(N)입니다. 정거장 번호가 항상 증가하는 방향으로만 이동한다는 조건 덕분에 단순한 순차 갱신만으로 최적해를 보장할 수 있습니다.