leetcode 알고리즘 - 64. Minimum Path Sum

Minimum Path Sum

☞ 문제링크

크기가 m,n인 2차원 배열의 좌측 상단(0,0)부터, 우측 하단(m-1,n-1) 까지 이동하는데, 이동 경로의 배열 값들을 모두 더하게 되는 경우, 이 값의 최소 값을 구하는 문제입니다. 예시로 들어둔 배열은 아래와 같습니다. 괄호안에는 좌표를 표시했습니다.

1  (0,0)	3 (0,1)	1 (0,2)
1 (1,0)	5 (1,1)	1 (1,2)
4 (2,0)	2 (2,1)	1 (2,2)

각 좌표들의 최소 합은 다음과 같이 구할 수 있습니다.

• 좌표가 0,0 인 경우는 항상 그 좌표의 값과 같습니다. (경우의 수가 1개)
• 좌표가 (0,x) 혹은 (x,0) 처럼 0이 들어가는 경우도 경우의 수가 1개 뿐입니다. 바로 이전의 좌표 값만 더해주면 됩니다. 예를들어 0,1의 이동 경로 최소값은 0,0으로 부터 오는 방법 밖에 없으므로, 경로 최소 값은 4가 됩니다.
• 위의 경우가 아닌 좌표들의 경우, 현재 좌표의 왼쪽과 위쪽의 경로 값중의 작은 값을 더해주면 됩니다. 예를들어 (1,1)의 경우 왼쪽 좌표 (1,0)의 경로 최소 값이 2이고, 위쪽 좌표 (0,1)의 경로 최소 값이 4가 됩니다. 2가 4보다 작은 경로 값이니 2를 더해주면 됩니다. 그러므로 (1,1)의 경로 최소 값은 2+5 = 7이 됩니다.

위와 같은 과정을 진행하여 모든 좌표들의 경로 최소 값을 구하고, 우측 하단 (2,2)의 값을 반환 해주면 됩니다.

풀이 방법을 찬찬히 보면 어렵지 않지만, 이런걸 어떻게 생각하냐구요? 그냥 동적계획법 그리드 알고리즘 문제 중 위와 같은 풀이가 굉장히 많습니다. ㅋㅋ 하나의 유형이라고 생각하시고 풀이 방법을 암기 하는 것이 정신건강에 이롭다고 생각됩니다.

풀이 코드 (java)

class Solution {
    public int minPathSum(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (i == 0 && j == 0) {
                    continue;
                } else if (i == 0) {
                    grid[i][j] += grid[i][j - 1];
                    continue;
                } else if (j == 0) {
                    grid[i][j] += grid[i - 1][j];
                    continue;
                } else {
                    grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);
                }
            }
        }

        return grid[grid.length-1][grid[0].length-1];
    }
}

배운점

• 동적 계획법 문제 유형 중의 그리드를 이용한 정형화된 문제 풀이 방법을 알게 되었다. 동적 계획법이라고 모두 재귀를 활용한 완전 탐색을 사용하는 것이 아니라는 것을 배웠다. (https://leetcode.com/problems/minimum-falling-path-sum/)