Python으로 푸는 LeetCode 63. Unique Paths II (Medium)

이 문제는 LeetCode 62. Unique Paths 문제의 다음 단계의 문제이다.

(0,0)부터 맨 아래의 오른쪽 끝부분까지 도달하는 경우의 수를 구해야 하며

중간에 장애물이 있는 경우를 고려해서 코드를 짜야 한다.

LeetCode 62. Unique Paths 문제풀이 보기

LeetCode에서 푼 문제 리스트 보기

LeetCode에서 문제 보기

github에서 코드 보기

문제 풀이

LeetCode 62. Unique Paths (문제 풀이 보기) 의 코드에서 장애물이 있는 경우에 대한 예외처리를 해주면 된다. 장애물이 있는 경우에는 해당 지점까지 올 수 있는 경우의 수를 0으로 초기화해주어서 해당 위치에 값을 입력해주면 된다.

파이썬 코드

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid) -> int:
        """
        Rumtime : faster than 70.44% of Python3
        Memory Usage : less than 5.19% of Python3
        """
        direction = [(0,-1), (-1, 0)]
        r = len(obstacleGrid)
        c = len(obstacleGrid[0])
 
        if obstacleGrid[0][0] == 1:
            return 0
 
        for i in range(r):
            for j in range(c):
                # 맨 처음만 예외처리
                if i == 0 and j == 0:
                    obstacleGrid[0][0] = 1
                    continue
 
                # 장애물은 진입이 안되므로 0으로 처리
                if obstacleGrid[i][j] == 1:
                    obstacleGrid[i][j] = 0
                    continue
 
                for next_pos in direction:
                    add_r, add_c = next_pos
                    temp_r = i + add_r
                    temp_c = j + add_c
                    if temp_r < 0 or temp_c < 0 or r <= temp_r or c <= temp_c:
                        continue
                    obstacleGrid[i][j] += obstacleGrid[temp_r][temp_c]
        print(obstacleGrid[r-1][c-1])
        return obstacleGrid[r-1][c-1]
 
s = Solution()
 
obstacleGrid = [
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
 
obstacleGrid = [
  [0,0,1],
  [0,1,0],
  [1,0,0]
]
 
s.uniquePathsWithObstacles(obstacleGrid)