[LeetCode] 64. Minimum Path Sum - 깊이우선탐색(DFS) + 동적계획법(Dynamic Programming) JAVA

https://leetcode.com/problems/minimum-path-sum/description/

코드설명

깊이우선탐색(DFS) + 동적계획법(Dynamic Programming) 을 활용합니다.

 

점화식을 사용하여 해결하는 방법의 경우,

최소합을 구하기 위해 실제로 최소값을 더해가면서 구하면 됩니다.

그 과정에서

1. 첫번쨰 열과 첫번쨰 행에 대하여 누적합을 계산합니다.

2. 나머지 칸들, 즉 (1,1) ~ (M, N)에 대하여 더 작은 합들로 갱신시켜나가면 됩니다.

 

DFS를 활용하는 경우에는, DFS(r, c) = (r,c)에서의 위치에서의 최소값을 반환한다 라고 정의하여, 문제를 해결합니다.

해당 코드에서 실수할만한 부분은 아래입니다. 

ret = Math.min(ret, DFS(grid, nr, nc, cache) + grid[r][c]);
// ret = Math.min(ret, DFS(grid, nr, nc, cache) ) + grid[r][c]; 틀린코드

+ grid[r][c]는 현재 위치의 값을 더해주는 연산입니다.

당연히, 현재 위치의 값을 DFS(r, c)와 함께 경로에 포함되어 연산시켜야만 올바르게 연산됩니다.

ret값이 처음으로 갱신된경우는, 아마 올바르게 갱신되는 것처럼 보입니다.

하지만, ret값은 다른경로 + 현재 위치값으로 올바르게 갱신되었지만, 이후에 비교될경우에는 grid값이 연산 이후에 비교되므로 올바르지 않음을 알 수 있습니다. (즉, 두번쨰 비교시에는 grid[r][c]가 포함되어 비교되지 않습니다.)

아래 예제를 직접 돌려보면 알 수 있습니다. 

 

1 2
1 1

 

코드

정답코드1입니다.

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        for(int i=1; i<m; i++){
            grid[i][0] += grid[i-1][0];
        }
        for(int j=1; j<n; j++){
            grid[0][j] += grid[0][j-1];
        }

        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                grid[i][j] = grid[i][j] + Math.min(grid[i-1][j], grid[i][j-1]);
            }
        }

        return grid[m-1][n-1];
    }
}

 

 

정답코드2입니다.

class Solution {
    public int minPathSum(int[][] grid) {
        int[][] cache = new int[201][201];
        for(int i=0; i<cache.length; i++){
            Arrays.fill(cache[i], -1);
        }
        DFS(grid, 0, 0, cache);
        return DFS(grid, 0, 0, cache);
    }

    int DFS(int[][] grid, int r, int c, int[][] cache){
        if(r == grid.length - 1 && c == grid[r].length - 1){
            return grid[r][c];
        }
        if(cache[r][c] != -1) return cache[r][c];

        int ret = Integer.MAX_VALUE;
        for(int[] dir : new int[][]{ {1, 0}, {0, 1}}){
            int nr = r + dir[0];
            int nc = c + dir[1];

            if(nr >= grid.length || nc >= grid[r].length) continue;
            ret = Math.min(ret, DFS(grid, nr, nc, cache) + grid[r][c]);
        }
        return cache[r][c] = ret;
    }

}