leetcode 64. Minimum Path Sum 풀이

문제 : m x n 으로 이루어진 grid 가 주어질때 (0,0)에서 출발하여 (m-1, n-1) 에 x, y 좌표로 한칸 씩만 이동할 수 있을 때 path에 있는 grid 값의 합이 최소가 되는 (m-1, n-1) 의 값을 반환하라.

ex) 

Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7

Follow up : -

 

아이디어 : 처음에는 경로 탐색으로 생각해서 BFS로 풀었지만 input이 커지자 timeout 이 발생했다. 아무래도 dp로 풀어야되는거 같은데 아이디어가 떠오르지 않았다.

 

코드 :

 

BFS로 푼 timeout이 발생하는 코드

from collections import deque

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        q = deque()
        m = len(grid)
        n = len(grid[0])
        visit = [[-1 for i in range(n)] for j in range(m)]
        d = [[1, 0], [0, 1]]
        q.append((0,0,grid[0][0]))
        visit[0][0] = grid[0][0]
        while q:
            y, x, s = q.popleft()
            for dd in d:
                dy = y + dd[0]
                dx = x + dd[1]
                if m <= dy:
                    continue
                if n <= dx:
                    continue
                t = s + grid[dy][dx]
                if visit[m-1][n-1] != -1 and visit[m-1][n-1] < s:
                    continue
                elif visit[dy][dx] == -1:
                    visit[dy][dx] = t
                elif t < visit[dy][dx]:
                    visit[dy][dx] = t
                else:
                    continue
                q.append((dy, dx, t))
        return visit[m-1][n-1]

 

풀이를 보고 다시 짠 코드

 

O(n^n) 의 시간복잡도를 가지는 dp 풀이 방식이다. 가장 자리의 값을 갱신한 후, 나머지 값에 대해 갱신한다.

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = 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[m-1][n-1]

학습 포인트 : 이 문제의 경우는 문제의 틀을 외우는게 좀 더 도움이 될거같다. 풀이를 모를 때 이러한 dp 문제를 풀기는 어려울거같다.

 

출처 : leetcode.com/problems/minimum-path-sum/