LeetCode 64. Minimum Path Sum with Python

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

 

 

bfs로 접근했다가 시간초과가 났던 문제

생각해보니까 그럼 앞서 갔던 길들을 최적으로 다시 다 바꿔줘야해서 bfs를 사용하면 안된다는 생각이 들었다.

그러다 생각이 든게 어짜피 오른쪽, 아래쪽으로밖에 움직이지 않으니까

위 한줄, 왼쪽 한줄의 비용을 미리 계산해놓고 위에서 오는게 cost가 적은지 왼쪽에서 오는게 cost가 적은지 판단하면 된다고 생각했다.

 

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """

        # 그래프의 가로 길이
        m = len(grid[0])
        # 그래프의 세로 길아
        n = len(grid)

        costs = [[0 for _ in range(m)] for _ in range(n)]
        costs[0][0] = grid[0][0]

        # 위 1줄, 왼쪽 1줄 cost 계산
        for i in range(n):
            for j in range(m):
                if i == 0 and j > 0:
                    costs[i][j] = grid[i][j] + costs[i][j-1]
                elif j == 0 and i > 0:
                    costs[i][j] = grid[i][j] + costs[i-1][j]

        for i in range(1, n):
            for j in range(1, m):
                costs[i][j] = min(grid[i][j] + costs[i-1][j], grid[i][j] + costs[i][j-1])
    
        return costs[n-1][m-1]