동적 계획법 응용 : 최소 비용 경로

∙ 최소 비용 경로 (minimum cost path)

- 2차원 행렬의 각 셀에 정수 값 비용이 적혀 있을 때, 행렬의 좌상단에서 우하단까지 이동하기 위한 최소 비용을 계산하는 문제. 최소 경로 합

- 이동은 오른쪽 또는 아래쪽 방향으로만 가능

 

∙ 문제 해결 방법

- 오른쪽 또는 아래쪽 방향으로만 이동할 수 있으므로, 임의이 좌표(x, y)에 도달하기 위해서는 (x-1,y) 또는 (x, y-1)좌표를 거쳐야 한다.

- 임의의 좌표 (x, y)에서의 행렬 값(비용)을 m(x, y)라고 하고, 좌상단에서 (x, y)까지 이동하는 경로의 최소 비용을 C(x, y)라고 할 경우 아래의 식이 성립된다.

C(x, y) =. min(C(x - 1, y), C(x, y - 1)) + m(x, y)

- 좌상단 좌표부터 시작하여 왼쪽에서 오른쪽으로, 위에서 아래 방향으로 C(x, y)값을 계산하고 최종적으로 우하단 좌표에서의 C(x, y)값을 구한다.

 

∙ 최소 비용 경로 솔루션 함수 코드

int solution(vector<vector<int>> m)
{
	int rows = (int)m.size();
    int cols = (int)m[0].size();
    
    vector<vector<int>> dp(rows, vector<int>(cols, 0);
    
    for (int y = 0; x < rows; y++){
    	for (int x = 0; x < cols; x++){
        	if (x == 0&& y ==0)
            	dp[x][y] = m[y][x];
            else if (x == 0)
            	dp[y][x] = dp[y - 1][x] + m[y][x];
            else if (y == 0)
            	dp[y][x] = dp[y][x - 1] + m[y][x];
            else
            	dp[y][x] = min(dp[y -1][x], dp[y][x -1]) + m[y][x];
            }
        }
        return dp[rows - 1][cols -1];
}

 

- 실행 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> m)
{
    int rows = (int)m.size();
    int cols = (int)m[0].size();
    
    vector<vector<int>> dp(rows, vector<int>(cols, 0));
    
    for (int y = 0; y < rows; y++){
        for (int x = 0; x < cols; x++){
            if (x == 0&& y ==0)
                dp[x][y] = m[y][x];
            else if (x == 0)
                dp[y][x] = dp[y - 1][x] + m[y][x];
            else if (y == 0)
                dp[y][x] = dp[y][x - 1] + m[y][x];
            else
                dp[y][x] = min(dp[y -1][x], dp[y][x -1]) + m[y][x];
            }
        }
        return dp[rows - 1][cols -1];
}

int main()
{
    vector<vector<int>> m = {
        {2, 7, 5, 4},
        {5, 3, 6, 8},
        {7, 8, 7, 4},
        {8, 1, 9, 5}
    };
    cout << "Minimum cost: " << solution(m) << endl;
}