파이썬으로 구현하는 최소 비용 경로(Min Cost Path) 알고리즘

이 글에서는 최소 비용 경로 문제를 해결하는 방법을 단계별로 살펴보겠습니다.

문제 정의

비용 행렬(cost matrix)과 목표 위치 (m, n)이 주어졌을 때, 시작점 (0, 0)에서 목표 지점까지 이동하는 경로 중 최소 비용을 구하는 것이 목표입니다. 여기서 각 칸(cell)의 값은 해당 칸을 지나갈 때 드는 비용을 의미합니다.

일반적으로 이동은 오른쪽, 아래, 그리고 대각선(오른쪽 아래) 방향으로 가능하며, 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다.

구현 예제

# 동적 계획법 접근
R = 3
C = 3
def minCost(cost, m, n):
    # 초기화
    tc = [[0 for x in range(C)] for x in range(R)]
    # 기저 사례(base case)
    tc[0][0] = cost[0][0]
    # 첫 번째 열의 누적 비용 계산
    for i in range(1, m + 1):
        tc[i][0] = tc[i-1][0] + cost[i][0]
    # 첫 번째 행의 누적 비용 계산
    for j in range(1, n + 1):
        tc[0][j] = tc[0][j-1] + cost[0][j]
    # 나머지 영역의 누적 비용 계산
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + cost[i][j]
    return tc[m][n]
# 메인 실행부
cost = [[1, 5, 3],
        [7, 7, 4],
        [8, 5, 3]]
print("Total Cost:", minCost(cost, 2, 1))

실행 결과

Total Cost: 13

코드 설명

위 코드의 핵심 로직은 다음과 같습니다.

1. 초기화 및 기저 사례: tc 배열은 (0, 0)부터 각 위치까지 도달하는 데 드는 최소 누적 비용을 저장합니다. 시작점인 tc[0][0]은 행렬 자체의 값으로 설정합니다.

2. 경계 처리: 첫 번째 열과 첫 번째 행은 이전 칸에서 한 방향으로만 이동할 수 있으므로, 이전 누적 비용에 현재 칸의 비용을 더해 순차적으로 계산합니다.

3. 점화식 적용: 나머지 모든 칸에 대해서는 왼쪽 대각선 위(tc[i-1][j-1]), 위쪽(tc[i-1][j]), 왼쪽(tc[i][j-1]) 세 방향 중 최솟값을 선택한 뒤 현재 칸의 비용을 더합니다.

모든 변수는 지역 범위(local scope) 내에서 선언되며, 실행 흐름에 따라 참조됩니다.

시간 복잡도

이 알고리즘은 행렬의 모든 칸을 한 번씩만 계산하므로 시간 복잡도는 O(m × n), 공간 복잡도 역시 O(m × n)입니다. 만약 원본 행렬을 수정해도 된다면 추가 배열 없이 제자리(in-place) 계산으로 공간을 절약할 수도 있습니다.

마무리

이번 글에서는 파이썬을 활용해 최소 비용 경로(Min Cost Path) 문제를 동적 계획법으로 해결하는 방법을 알아보았습니다. 격자 형태의 경로 탐색 문제에서 널리 활용되는 패턴이므로, 유사한 DP 문제를 풀 때 큰 도움이 될 것입니다.