문제 개요
이번 글에서는 C 언어로 최소 비용 경로(Minimum Cost Path) 문제를 해결하는 방법을 살펴보겠습니다. 2차원 행렬의 각 칸에는 이동 비용이 부여되어 있으며, 왼쪽 상단 모서리에서 출발해 오른쪽 하단 모서리에 도달하는 경로 중 이동 비용이 최소인 경로를 찾아야 합니다. 단, 임의의 칸에서는 아래쪽 또는 오른쪽 칸으로만 이동할 수 있습니다.
이 문제는 단순 재귀 호출보다 동적 계획법(Dynamic Programming)으로 접근하는 것이 훨씬 효율적입니다.
비용 행렬 cost[ ][ ]와 위치 (m, n)이 주어졌을 때, (0, 0)에서 (m, n)까지 도달하는 최소 비용 경로의 값을 반환하는 함수를 작성해야 합니다. (m, n)에 도달하는 경로의 총 비용은 그 경로에 포함된 모든 칸의 비용 합계(출발지와 목적지 포함)입니다.
가정 − 모든 비용은 양수이며, 입력 행렬에는 음수 비용 사이클이 존재하지 않습니다.
예시
(2, 2) 지점까지의 최소 비용 경로를 구해 보겠습니다.
각 칸의 비용은 이미지에 표시되어 있습니다. 최적 경로는 (0, 0) ⇒ (0, 1) ⇒ (1, 2) ⇒ (2, 2)이며, 경로의 총 비용은 8(1 + 2 + 2 + 3)입니다.
접근 방법
주어진 행렬과 같은 크기의 답안 행렬(solution)을 생성한 뒤, 이를 바텀업(bottom-up) 방식으로 채워 나갑니다.
행렬 arrA[ ][ ]가 주어졌을 때 각 칸에서는 두 가지 선택지(오른쪽 이동 또는 아래 이동)가 있으며, 임의의 칸 (i, j)에서는 두 값 중 더 작은 것을 선택하면 됩니다.
solution[i][j] = A[0][j] (i = 0, 첫 번째 행)
= A[i][0] (j = 0, 첫 번째 열)
= A[i][j] + Min(solution[i-1][j], solution[i][j-1]) (i > 0 && j > 0)
동적 계획법을 적용하면 위 점화식을 활용해 이 문제를 효율적으로 해결할 수 있습니다. 크기 m × n의 최소 비용 경로 테이블을 만들고 다음과 같이 정의합니다.
minimumCostPath[i][j] = (0, 0)에서 (i, j)에 도달하기 위한 최소 비용
경계 조건은 다음과 같습니다.
minimumCostPath[0][0] = costMatrix[0][0] minimumCostPath[i][0] = minimumCostPath[i - 1][0] + costMatrix[i][0] (모든 i > 0) minimumCostPath[0][j] = minimumCostPath[0][j - 1] + costMatrix[0][j] (모든 j > 0)
이후 앞서 정의한 점화식을 적용해 최소 비용 경로 행렬을 순서대로 채웁니다. 이전 단계의 값들은 이미 행렬에 계산되어 저장되어 있으므로, 재귀 방식처럼 같은 값을 반복해서 다시 계산할 필요가 없습니다.
minimumCostPath[i][j] = costMatrix[i][j] + min(minimumCostPath[i - 1][j - 1],
minimumCostPath[i - 1][j],
minimumCostPath[i][j - 1])
여기서 minimumCostPath[i][j]를 계산할 때 세 인접 값(minimumCostPath[i - 1][j - 1], minimumCostPath[i - 1][j], minimumCostPath[i][j - 1])을 사용하는 이유는, 이동 규칙상 (i, j) 칸에 도달할 수 있는 유일한 칸들이기 때문입니다. 최종적으로 minimumCostPath[m][n]을 반환하면 됩니다.
이 동적 계획법 알고리즘의 시간 복잡도는 O(mn)입니다.
구현 예제
다음은 위 알고리즘을 구현한 예제 코드입니다. (입출력 편의를 위해 C++ 스타일의 iostream을 사용했습니다.)
#include <iostream>
using namespace std;
int min_(int a, int b, int c){
if (a < b)
return (a < c) ? a : c;
else
return (b < c) ? b : c;
}
int min_cost(int cost[4][4], int m, int n){
int i, j;
int tot_cost[4][4];
tot_cost[0][0] = cost[0][0];
for (i = 1; i <= m; i++)
tot_cost[i][0] = tot_cost[i - 1][0] + cost[i][0];
for (j = 1; j <= n; j++)
tot_cost[0][j] = tot_cost[0][j - 1] + cost[0][j];
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
tot_cost[i][j] = min_(tot_cost[i - 1][j - 1], tot_cost[i - 1][j], tot_cost[i][j - 1]) + cost[i][j];
return tot_cost[m][n];
}
int main(){
int cost[4][4] = {
{ 9, 9, 4 },
{ 8, 0, 9 },
{ 1, 2, 8 }
};
cout<<" The minimum cost is "<<min_cost(cost, 2, 2);
return 0;
}
실행 결과
The minimum cost is 17