서로 다른 비용이 기록된 행렬(matrix)이 주어지고, 목적지 셀(destination cell)의 좌표도 함께 제공됩니다. 이때 시작 셀인 (0, 0)에서 목적지 셀까지 이동하는 최소 비용 경로를 찾아야 합니다.
행렬의 각 셀은 해당 셀을 통과할 때 드는 비용을 의미합니다.
한 셀에서 임의의 방향으로 자유롭게 이동할 수는 없습니다. 이동 가능한 방향은 다음 세 가지뿐입니다.
- 오른쪽 셀
- 바로 아래 셀
- 오른쪽 아래 대각선 셀
입력과 출력
입력:
비용 행렬과 목적지 좌표. 이 예제에서 목적지는 (2, 2)입니다.
1 2 3
4 8 2
1 5 3
출력:
(0, 0)에서 목적지까지 도달하는 최소 비용. 최소 비용은 8입니다.
알고리즘
minCostPath(destX, destY, cost)
입력 − 목적지의 (x, y) 좌표와 비용 행렬(cost matrix)
출력 − 목적지에 도달하기 위한 최소 비용
이 알고리즘은 동적 계획법(Dynamic Programming)을 활용합니다. 각 셀까지의 누적 최소 비용을 저장하는 totalCost 행렬을 만들고, 왼쪽·위쪽·왼쪽 위 대각선 방향의 값 중 최솟값에 현재 셀의 비용을 더해 차례대로 채워 나갑니다. 시간 복잡도는 행렬 크기가 m×n일 때 O(mn)입니다.
Begin
cost 행렬과 같은 크기의 totalCost 행렬 정의
totalCost[0, 0] = cost[0, 0]
// 첫 번째 열 초기화
for i := 1 to destX, do
totalCost[i, 0] := totalCost[i-1, 0] + cost[i, 0]
done
// 첫 번째 행 초기화
for j := 1 to destY, do
totalCost[0, j] := totalCost[0, j-1] + cost[0, j]
done
// 나머지 모든 셀 계산
for all places (i, j) from (1, 1) to (destX, destY), do
totalCost[i, j] := minimum(totalCost[i-1, j-1], totalCost[i-1, j], totalCost[i, j-1]) + cost[i, j]
done
return totalCost[destX, destY]
End
예제 코드 (C++)
#include<iostream>
#define ROW 3
#define COL 3
using namespace std;
int cost[ROW][COL] = {
{1, 2, 3},
{4, 8, 2},
{1, 5, 3}
};
int min(int a, int b, int c) {
return (a<b)?((a<c)?a:c):((b<c)?b:c);
}
int minCostPath(int destX, int destY) {
int totalCost[ROW][COL];
totalCost[0][0] = cost[0][0];
for (int i = 1; i <= destX; i++)
totalCost[i][0] = totalCost[i-1][0] + cost[i][0]; // totalCost 배열의 첫 번째 열 설정
for (int j = 1; j <= destY; j++) // totalCost 배열의 첫 번째 행 설정
totalCost[0][j] = totalCost[0][j-1] + cost[0][j];
for (int i = 1; i <= destX; i++) // 두 번째 행과 열부터 끝까지 계산
for (int j = 1; j <= destY; j++)
totalCost[i][j] = min(totalCost[i-1][j-1], totalCost[i-1][j], totalCost[i][j-1]) + cost[i][j];
return totalCost[destX][destY];
}
int main() {
cout << "Minimum Cost: "<< minCostPath(2, 2); // 목적지 (2, 2)
return 0;
}
실행 결과
Minimum Cost: 8
위 예제에서 (0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2) 경로를 따라 이동하면 비용이 1 + 4 + 1 + 5 + 3으로 계산되지만, 실제 최적 경로는 대각선 이동을 활용하여 총 비용 8로 목적지에 도달하게 됩니다. 이처럼 동적 계획법을 사용하면 모든 경로를 일일이 탐색하지 않고도 효율적으로 최소 비용을 구할 수 있습니다.