64. Minimum Path Sum

64. Minimum Path Sum

 

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # grid의 행(row) 개수를 계산
        rows = len(grid)
        # grid의 열(column) 개수를 계산
        cols = len(grid[0])

        # 첫 번째 열의 값을 누적합으로 업데이트 (위에서 아래로 이동)
        for r in range(1, rows):
            grid[r][0] += grid[r-1][0]  # 현재 위치 값을 바로 위 값과 더함
        
        # 첫 번째 행의 값을 누적합으로 업데이트 (왼쪽에서 오른쪽으로 이동)
        for c in range(1, cols):
            grid[0][c] += grid[0][c-1]  # 현재 위치 값을 바로 왼쪽 값과 더함

        # 나머지 셀들을 업데이트 (최소 경로를 기준으로 값을 갱신)
        for r in range(1, rows):  # 첫 번째 행 이후의 행을 순회
            for c in range(1, cols):  # 첫 번째 열 이후의 열을 순회
                # 위쪽 셀(grid[r-1][c])과 왼쪽 셀(grid[r][c-1]) 중 더 작은 값을 선택해 현재 값에 더함
                grid[r][c] += min(grid[r-1][c], grid[r][c-1])

        # 최소 경로의 총합은 마지막 셀(grid[rows-1][cols-1])에 저장됨
        return grid[rows-1][cols-1]

 

 

동작 방식

1. 첫 번째 열 업데이트:
   • 위에서 아래로 내려가며, 각 셀의 값을 이전 셀과 더해 누적합으로 변경합니다.
2. 첫 번째 행 업데이트:
   • 왼쪽에서 오른쪽으로 이동하며, 각 셀의 값을 이전 셀과 더해 누적합으로 변경합니다.
3. 나머지 셀 업데이트:
   • 각 셀의 값을 최소 경로를 기준으로 업데이트합니다. 해당 셀로 도달하기 위해 필요한 최소 비용을 계산합니다.
4. 결과 반환:
   • 마지막 셀(grid[rows-1][cols-1])에는 최소 경로 합이 저장됩니다.

 

https://youtu.be/pGMsrvt0fpk?si=VF30DpesXJadj8p-

 

2차: 2025.01.03 - 이제 그냥 풀림

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        R, C = len(grid), len(grid[0])

        for r in range(1, R):
            grid[r][0] += grid[r-1][0]

        for c in range(1, C):
            grid[0][c] += grid[0][c-1]

        for r in range(1, R):
            for c in range(1, C):
                grid[r][c] += min(grid[r-1][c], grid[r][c-1])

        return grid[R-1][C-1]