[LeetCode] 63. Unique Paths Ⅱ풀이 및 코드

문제

이전 글에서 푼 Unique Paths(https://june-coder.tistory.com/5?category=913762)에 약간의 제약사항이 추가된 문제이다. 이전에는 시작점에서 도착점까지 가능한 경로의 개수를 구하면 되었지만, 이번 문제에서는 지도에 방해물이 추가된다. 따라서 방해물을 지나지 않는 경로의 개수를 세어야 한다.

---

풀이

문제 자체는 평이했다. 이전 문제를 푼 방법대로, 특정 지점의 윗 칸과 왼쪽 칸의 경로의 개수를 합하면 된다. 이 문제에서는 방해물이 있기 때문에 왼쪽이나 위에 방해물이 있으면 해당 경로로는 오지 못하는 것을 의미하기 때문에 그 경로를 제외한 나머지 경로를 구하면 된다.

그러나 약간 어려웠던 부분은 예외 처리이다. 만약 [[1]]와 같은 입력이 들어온다면 답은 무엇이 되어야 할까? 답은 0이 되어야 한다. 로봇이 갈 수 있는 경로가 없기 때문이다. 만약 [[1, 0]]이 입력이라면? 마찬가지로 0이다. 출발지점이 막혀 있기 때문이다. [[0, 1]]은? 마찬가지로 0이다.

---

코드

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                elif i == 0 or j == 0:
                    if i > 0 and dp[i-1][j] == 0:
                        dp[i][j] = 0
                    elif j > 0 and dp[i][j-1] == 0:
                        dp[i][j] = 0
                    else:        
                        dp[i][j] = 1    
                elif obstacleGrid[i-1][j] == 1 or obstacleGrid[i][j-1] == 1:
                    if obstacleGrid[i-1][j] == 1 and obstacleGrid[i][j-1] == 1:
                        dp[i][j] = 0
                    elif obstacleGrid[i-1][j] == 1:
                        dp[i][j] = dp[i][j-1]
                    else:
                        dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]                    
                    
        return dp[m-1][n-1]

---

리트코드 제출 결과

---

출처

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