[LeetCode]Minimum Path Sum

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

Minimum Path Sum - LeetCode

 

문제 분석

주어진 m*n grid에서 오른쪽 or 아래로만 이동할 수 있습니다. 가장 왼쪽 위에서 가장 오른쪽 아래로 이동하는 경로의 합이 가장 적은 값을 구하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        for row_idx, row in enumerate(grid):
            for col_idx, col in enumerate(row):
                if row_idx != 0 and col_idx != 0:
                    grid[row_idx][col_idx] = min(grid[row_idx-1][col_idx], grid[row_idx][col_idx-1]) + grid[row_idx][col_idx]
                else:
                    if row_idx == 0 and col_idx == 0:
                        continue

                    if row_idx == 0:
                        grid[row_idx][col_idx] = grid[row_idx][col_idx-1] + grid[row_idx][col_idx]

                    if col_idx == 0:
                        grid[row_idx][col_idx] = grid[row_idx-1][col_idx] + grid[row_idx][col_idx]

        return grid[-1][-1]

접근 방법

1. grid를 이중 순회합니다. 
2. (0, 0) 지점이 아니라면
   1. (i-1, j), (i, j-1) 중 작은 값과 현재 값을 더해서 grid를 갱신합니다.
3. (0, 0) 지점이라면 건너뜁니다.
4. row_idx만 0이라면 
   1. (i, j-1)에 현재 값을 더해서 grid를 갱신합니다.
5. col_idx만 0이라면
   1. (i-1, j)에 현재 값을 더해서 grid를 갱신합니다.
6. 가장 오른쪽 아래에 위치한 값이 최소 값입니다.

이 문제는 DP 문제입니다. Grid를 보고 각 좌표에서의 최소 합을 구해보다보면 일종의 규칙을 찾을 수 있습니다.

(x, y) 위치까지 오기위한 최소 값은 (x-1, y) + (x, y) 와 (x, y-1) + (x, y) 중 더 작은 값을 고르면 됩니다. 그리고 0이 들어가는 인덱스의 경우에는 따로 예외처리를 해주면서 반복문을 순회하면 최소 합을 구할 수 있습니다.