leetcode 63. Unique Paths II 풀이

문제 : 0,0에서 시작하여 오른쪽 아래 끝칸으로 한칸씩 이동할때, 장애물 좌표계가 주어진다. 마지막 지점에 도달할 수 있는 unique path의 합을 반환하라

 

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right

Follow up :

 

아이디어 : unique path 1번 문제에서 장애물 요소를 추가하면 된다. 장애물 만날시 해당 좌표의 unique path 를 0 으로 만들면서 진행하면 쉽게 풀린다.

 

코드 :

 

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            if obstacleGrid[i][0] == 1:
                break
            dp[i][0] = 1
        for i in range(n):
            if obstacleGrid[0][i] == 1:
                break
            dp[0][i] = 1
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        #print(dp)
        return dp[m-1][n-1]

 

학습 포인트 : 이런 류의 dp 문제는 풀이법을 외워두는게 더 편한거같다.

 

출처 : leetcode.com/problems/unique-paths-ii/