LeetCode 64(Minimum Path Sum, Python)

1. 문제 링크

• Minimum Path Sum - LeetCode

Minimum Path Sum - LeetCode

2. 문제 설명

• m*n 격자에 정수가 주어져있고 가장 왼쪽 위에서 출발해서 오른쪽 또는 아래 방향으로만 이동하여 가장 오른쪽 아래로 이동할 때, 이동하며 지난 칸의 수의 합의 최솟값 구하기 문제
• 예시) 아래 상황에서는 1, 3, 1, 1, 1을 따라가면 합이 최소이고 그 값은 7이다.

3. 처음 풀이

• 주어진 값을 수열의 일반항 an이라 생각하고 부분합 Sn을 구하는 문제이다.
• 1행의 [1, 3, 1]의 부분합을 생각하여 [1, 4, 5]로 만든다.
• 1열의 [1, 1, 4]의 부분합을 생각하여 [1, 2, 6]로 만든다.

 1 4 5
 2 ?
 6

• 그 다음에는 각 칸의 위쪽 값과 왼쪽 값 중 작은 값과 그 칸의 값을 더한다.
• 즉, 2행 2열에 5가 있는데 그 위에는 4, 왼쪽에는 2가 있으므로 작은 2에 5를 더하여 ? 위치에 7이 들어간다. 마찬가지로 반복하면 마지막 값이 원하는 값이다.

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:

        result = [[[]]*len(grid[0]) for _ in range(len(grid))]

        for col in range(len(grid[0])):
            if col == 0:
                result[0][col] = grid[0][col]
            else:
                result[0][col] = result[0][col - 1] + grid[0][col]
 
        for row in range(len(grid)):
            if row == 0:
                result[row][0] = grid[row][0]
            else:
                result[row][0] = result[row - 1][0] + grid[row][0]

        for row in range(1, len(grid)):
            for col in range(1, len(grid[row])):
                result[row][col] = min(result[row-1][col], result[row][col - 1]) + grid[row][col]
        
        return result[-1][-1]

4. 다른 풀이

• 핵심 로직은 같다. 1행 1열만 따로 처리하면 for문이 좀 더 예뻐진다.

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
            
        
        m, n = len(grid), len(grid[0])
        
        for i in range(1, m):
            grid[i][0] += grid[i-1][0]
        
        for i in range(1, n):
            grid[0][i] += grid[0][i-1]
        
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        
        return grid[-1][-1]

---

• 추가로 result 행렬 만들지 말고 grid를 변형하여 in-place로 반환

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        n=len(grid)
        m=len(grid[0])
        for i in range(n):
            for j in range(m):
                if i==0:
                    if j!=0:
                        grid[i][j]+=grid[i][j-1]
                elif j==0:
                    if i!=0:
                        grid[i][j]+=grid[i-1][j]
                else:
                    grid[i][j]+=min(grid[i-1][j],grid[i][j-1])
        return grid[n-1][m-1]

5. 배운 점

• in-place 로 가능하구나.
• 런타임 뿐 아니라 공간복잡도를 최적화하려 시도하자.