[LeetCode] Java - 64. Minimum Path Sum (DFS + DP 기본문제)

이번 SSAFY 계절학기에서 진행한 알고리즘 특강 내용을 간단하게 정리했습니다!

 

우선 DFS와 메모이제이션을 사용한 다이나믹 프로그래밍입니다.

주어진 문제에서 N이 30이하일때 모든 경우를 탐색해야하는경우, 단순히 DFS만을 통해 문제를 풀수없는 경우가 있습니다. 이때 반드시 메모이제이션을 활용해야 문제를 풀수있습니다.

 

아래와 같은 문제를 통해 Top-down 방식으로 메모이제이션을 연습했습니다.

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

Minimum Path Sum - LeetCode

(0,0)에서 시작하여 (R-1,C-1)로 도착할때까지 최소 비용으로 가는 경로를 찾아야한다.

 

Top-down 방식이기 때문에 반대로 (R-1,C-1)에서부터 출발하여 (0,0)으로 가는 최소 비용이 memo 배열에 차례대로 저장된다. Bottom-up 방식으로 푼다면 (0,0)~(R-1, C-1) 순서대로 값이 계산된다. 마찬가지로, Top-down 방식이기때문에 기저조건은 (R-1,C-1)에 도착했을때 해당 map의 비용이 리턴된다.

 

(Top-down 기법은 뒤에서부터 값이 계산된다는것을 이미 알고 있기 때문에 아예 시작지점을 (R-1,C-1)로 하고 기저조건을 (0,0)으로 하는게 더 직관적일것같다.)

 

문제에서 도착지점까지 가는 방향은 아래, 오른쪽 방향 두가지로 존재한다.

따라서, memo[y][x] 배열에 계산된 값이 적혀있다면 바로 리턴하고, memo[y][x]에 메모되있지 않다면 min(아래로가는경우, 오른쪽으로 가는 경우) + 현재위치에서의 비용을 계산하여 memo에 적어준다.

 

findMinPath(grid, 0, 0, memo)는 memo[y][x]를 리턴하기때문에 바로 답으로 리턴해도되고, memo[0][0]으로 리턴해도 정답이다.

Java Code

class Solution {
    public int minPathSum(int[][] grid) {
        int R = grid.length;
        int C = grid[0].length;
        int[][] memo = new int[R][C];
        
        int ans = findMinPath(grid, 0,0, memo);
        
        return ans;
    }
    
    private static int findMinPath(int[][] grid, int y, int x, int[][] memo){
        if(y >= grid.length || x >= grid[0].length) return Integer.MAX_VALUE;
        if(y == grid.length-1 && x == grid[0].length-1) return grid[y][x];
        
        if(memo[y][x] != 0) return memo[y][x];
        
        int down = findMinPath(grid, y+1,x, memo);
        int right = findMinPath(grid, y,x+1, memo);
        
        memo[y][x] = Math.min(down, right) + grid[y][x];
        
        return memo[y][x];
    }
}

 

Python Code

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        R,C = len(grid), len(grid[0])
        memo = [[-1 for _ in range(C)] for _ in range(R)]
        
        def dfs(y,x):
            nonlocal R, C, grid, memo
            if y == 0 and x == 0:
                return grid[0][0]
            if y >= R or x >= C or y < 0 or x < 0:
                return sys.maxsize
            
            if memo[y][x] > 0:
                return memo[y][x]
            
            memo[y][x] = min(dfs(y-1,x) , dfs(y,x-1)) + grid[y][x]
            return memo[y][x]
            
            
        return dfs(len(grid)-1, len(grid[0])-1)