[DP 문제] LEETCODE 63. Unique Paths II

문제

https://leetcode.com/problems/unique-paths-ii/

문제풀이

각 위치 (row, col)에서, 만약 해당 위치에 장애물이 있다면 경로 수는 0로 처리한다.
(0, 0) 위치는 출발점이므로 경로 수를 1로 초기화한다.
첫 번째 행과 첫 번째 열의 위치에 대해서는, 해당 위치로의 경로 수는 이전 위치들로부터의 경로 수와 동일하게 처리한다.
나머지 위치들에 대해서는, 위쪽 위치와 왼쪽 위치로부터의 경로 수를 더한 값이 해당 위치의 경로 수가 된다.
최종적으로는 마지막 위치인 (m-1, n-1)의 경로 수가 최종 결과로 반환된다.

코드

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m,n,dp =len(obstacleGrid),len(obstacleGrid[0]), {}
        dp[(0,0)]=1
        for row in range(m):
            for col in range(n):
                if obstacleGrid[row][col]==1: 
                    dp[(row,col)]=0
                    continue
                if row==0 and col==0:
                    dp[(0,0)]=1
                    continue
                if row==0 and col>0:
                    dp[(row,col)]=dp[(row,col-1)]
                    continue
                if col==0 and row>0:
                    dp[(row,col)]=dp[(row-1,col)]
                    continue
                
                    
                    
                dp[(row,col)]=dp[(row-1,col)]+dp[(row,col-1)]
        return dp[(m-1,n-1)]
                

Lookback

1. 전형적인 DP 문제로써 해결에 큰 어려움이 없었다. 추가로 소스를 간결하게 작성하기 위해 dic={} 대신 defaultdict(int)을 선언하여 submit하였는데 기존 33ms 에서 56ms로 속도가 느려졌다. defaultdict에서 초기화 값을 선언/할당하는 데 추가로 시간 소요가 발생하였을 것으로 보인다. 속도 면에서 살짝 느려지는 부분이 있으나 알고리즘 문제 대회가 아니라면 defaultdict사용을 통해 간결한 소스로 운영하는 것이 더 이득이 될 것 같다.