[LeetCode 풀이/python] 63. Unique Paths II (medium)

문제 설명: 로봇이 m x n 형태 격자의 왼쪽 상단 (아래 그림에서 'Start' 표시된 곳) 에 위치해 있다. 이 로봇은 한 번에 아래 혹은 오른쪽 방향으로 한 칸 씩만 움직일 수 있으며, 격자의 오른쪽 하단 (아래 그림에서 'Finish' 표시된 곳) 에 도달하고자 한다. 이제 격자 위에 장애물들이 존재할 경우를 생각해보자. 이 때 고유한 경로는 얼마나 존재하는가? 장애물과 공간은 각각 1과 0 으로 표시되어 있다.

 

(A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and space is marked as 1 and 0 respectively in the grid.)

 

예시 1)

입력: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]  -->  출력: 2

설명: 격자 한가운데에 장애물이 하나 존재하므로, ▶▶▼▼ 와 ▼▼▶▶ 의 두 가지 경로가 가능함 

 

예시 2)

입력: obstacleGrid = [[0,1],[0,0]]  -->  출력: 1

 

제한 조건:

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 값은 0 또는 1.

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 장애물이 없는 경우에 대해 DP 를 이용한 풀이를 조금만 응용하면 된다..!
  • 기본적으로 (1, 1) 에서 (i, j) 까지 도달하는 경로 dp[i][j] 는 아래로 한 칸 내려오는 dp[i-1][j] 와 오른쪽으로 한 칸 이동하는 dp[i][j-1] 값의 합으로 구할 수 있으나, 해당 위치에 장애물이 존재하는 경우 지나갈 수 없는 길이 되므로 dp[i][j] 를 0 으로 만듦

 

• 코드 구현

def uniquePathsWithObstacles(obstacleGrid: List[List[int]]) -> int:
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [ [0]*(n+1) for _ in range(m+1) ]
        
    for i in range(1, m+1):
        for j in range(1, n+1):
            if (i == 1) and (j == 1) : 
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            
            if obstacleGrid[i-1][j-1] == 1: dp[i][j] = 0
                    
    return dp[-1][-1]

 

• 결과
  • O(m*n) 이지만 무난하게 통과...!
  • factorial 을 이용할 경우 장애물 개수가 많아짐에 따라 경우의 수를 고려하는 게 복잡해져서 효율적인 접근이 아닌 듯 ㅠ