골드에그

1. 문제요약

leetcode.com/problems/dungeon-game/

악마가 공주를 납치해 N x M 던전판 가장 우측 하단에 감금했다.

가장 좌측 상단에 있는 왕자가 공주를 구하기 위한 최소 체력은 얼마인지 구하시오.

룰은 다음과 같다.

① 왕자는 우측 또는 하단 방향으로만 한 칸씩 갈 수 있다.

② 각 방에는 음의 정수 또는 양의 정수가 있다. 왕자가 이동할 때 이 숫자에 영향을 받는다.

음수라면 숫자만큼 체력이 삭감되고, 양수라면 숫자만큼 체력이 상승한다.

③ 왕자 체력이 0 이거나 음수가 되면 게임은 종료된다.

2. 문제예제

3. 팩트추출

Fact 1 : N X M 던전판을 작게 축소하여 작은 문제들의 결합으로 구성할 수 있고 이 작은 문제들의 최적해들을 결합하면 전체 문제의 최적해가 된다. 따라서 Dynamic Programming 문제이다.

Fact 2 : dp[i,j] 를 dungeon[i,j] 에서 최소값이라고 할 때, dp[i,j] 는 dp[i,j+1] 과 dp[i+1,j] 중 최소값에 dungeon[i,j] 를 더한 값이다. dungeon[i,j] 값이 양수라면 0을 음수라면 절대값을 더한다. 문제에서 최소값을 구하라고 명시하고 있으므로 양수일 때는 신경 쓸 필요가 없다. 음수를 다 더한 값이 그 경로의 최소값이 된다.

Fact 3 : 일반적인 DP 문제와는 달리 해당 점화식에서 바로 값을 구할 수 없다. 점화식으로 표현되는 dp[i,j+1] , dp[i+1,j] 이 두 항이 다른 값들이 먼저 계산되어야 계산할 수 있기 때문이다. 그래서 기저 사례부터 먼저 구하고, 기저 사례만 필요한 마지막 행과 열을 구해 나머지 부분들을 계산하여야 한다.

Fact 4 : Top-Down 방식이던 Bottom-Up 방식이던 무한 루프를 방지하기 위해 기저 사례가 필요하다. 점화식으로 표현된 dp[i,j+1] 과 dp[i,j+1] 이 두 항이 이전 항들로 표현되지 않을 수 있을 때 기저 사례라고 한다. 이 문제에서는 공주가 있는 위치가 기저 사례이다.

4. 문제풀이(수동)

예제 1번을 기준으로 문제풀이를 진행한다.

기저 사례를 먼저 구하면, 공주 위치에 있는 값이 -5 이므로 6 이라는 최소 체력이 필요하다.  

(만약 값이 양수였다면 1 이라는 최소 체력이 필요할 것이다.)

Fact 3 에서 정리한 바와 같이 공주 위치를 기준으로 좌측 행 상단 열을 구하면 다음과 같다.

마지막 행과 마지막 열은 각각 이전 행과 이전 열 한 개씩만 필요하기 때문에 풀 수 있다.

이 값들을 기준으로 나머지 부분들도 계산하면,

최소 체력은 7 이라는 것을 알 수 있다.

5. 문제전략

위 수동풀이처럼 공주님 위치에서 마지막 행 열을 구한 후, 나머지 부분들을 계산할 수 밖에 없다.

Top-Down 방식, Bottom-Up 방식으로 모두 풀 수 있다.

6. 소스코드

Top-Down

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int row_size = dungeon.size();
        int column_size = dungeon[0].size();
        vector<vector<int>> dp(row_size, vector<int>(column_size));
        return calculate(dungeon, 0, 0, dp);
    }

    int calculate(vector<vector<int>>& dungeon, int i, int j, vector<vector<int>>& dp) {
        // 기저 사례
        if (i == dungeon.size() - 1 && j == dungeon[0].size() - 1)
            return dungeon[i][j] > 0 ? 1 : -dungeon[i][j] + 1;
        // 메모이제이션
        if (dp[i][j] != NULL)
            return dp[i][j];
        // 마지막 행
        if (i == dungeon.size() - 1)
            return dp[i][j] = max(1, calculate(dungeon, i, j + 1, dp) - dungeon[i][j]);
        // 우측 마지막 열
        if (j == dungeon[0].size() - 1)
            return dp[i][j] = max(1, calculate(dungeon, i + 1, j, dp) - dungeon[i][j]);

        return dp[i][j] = max(1, min(calculate(dungeon, i + 1, j, dp) - dungeon[i][j],
                calculate(dungeon, i, j + 1, dp) - dungeon[i][j]));
    }
}

Bottom-Up

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int r=dungeon.size();
        int c=dungeon[0].size();
        vector<vector<int>> dp(r,vector<int>(c));

        for(int i=r-1;i>=0;--i)
        {
            for(int j=c-1;j>=0;--j)
            {
                if(i==r-1 && j==c-1)     // 초기 값으로 맨 오른쪽 밑 (Princess Cell)
                    dp[i][j] = max(1,-dungeon[i][j]+1);
                else if(i==r-1)     // 마지막 행
                    dp[i][j] = max(1, dp[i][j+1]-dungeon[i][j]);
                else if(j==c-1)     // 우측 마지막 열
                    dp[i][j] = max(1, dp[i+1][j]-dungeon[i][j]);
                else
                    dp[i][j] = max(1,min(dp[i][j+1],dp[i+1][j])-dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
};