LeetCode_63. Unique Paths II

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

Unique Paths II - LeetCode

 

Solution1. 

 

2020/12/21 - [알고리즘/Leetcode] - LeetCode_62. Unique Paths 에서 장애물이 추가된 문제

 

이전과 동일하게 M x N 사이즈의 table을 이용하고 (r,c) 칸으로 이동할수 있는 경우는 아래와 같이 표현 가능하다.

 

table[r][c] = table[r-1][c] + table[r][c-1]

                    Down           Right

 

table의 초기화는 기조노가 다르게 0으로 초기화 한 뒹에 r=0인 모든 column 중에서 장애물을 만나기 전까지만 1로 초기화, 마찬가지로  c=0인 모든 row에 대해서 장애물을 만나기 전까지 1로 초기화 (장애물을 만나면 더 나아갈수 없으므로)

 

이후에는 (r,c) = (1,1) 부터 장애 물이 없는 경우에 대해서만 루프를 돌면서 table update

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        
        if obstacleGrid[0][0] == 1: return 0
        
        table = [[0]*(n) for _ in range(m)]

		for r in range(m):
            if obstacleGrid[r][0] == 0:
                table[r][0] = 1
            else:
                break
        
        for c in range(n):
            if obstacleGrid[0][c] == 0:
                table[0][c] = 1
            else:
                break
        
        for r in range(1,m):
            for c in range(1,n):
                if obstacleGrid[r][c] == 0:
                    table[r][c] = table[r-1][c] + table[r][c-1]   
        
        return table[-1][-1]