[LeetCode] 63. Unique Paths II

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 109.

 

Example 1:

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

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

 

Constraints:

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

반응형

---

이 문제는 62번 문제에서 장애물이 추가된 문제라고 볼 수 있다.

 

1. 최초 2중 for문을 통해 구하려고 했지만 [[0]]이나 한줄짜리 조건에 대한 경우를 빼먹어 wrong answer가 발생했다.

2. 장애물의 갯수가 1개로 지정되어 있다면 m,n을 구하고 좌상단에서 장애물, 장애물에서 우하단까지 길을 구해 빼면 되지만 장애물이 여러개가 나올 수 있어 다시 wrong answer가 발생했다.

3. 마지막으로 작성한 코드는 2중 for문을 돌며 2차원 배열에 과거 초등학교 수학문제 풀 듯 장애물이 없다면 x-1과 y-1의 값을 더하여 최종 유니크 길을 찾는 방식으로  작성했다. 상단과 좌우 끝열에 대한 조건을 추가하였다.

 

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        for i in range(0, m):
            for j in range(0, n):
                if obstacleGrid[i][j] == 1:
                    obstacleGrid[i][j] = 0
                else:
                    if i-1 < 0 and j-1 < 0:
                        obstacleGrid[i][j] = 1
                    elif i-1 < 0 and j-1 >= 0:
                        obstacleGrid[i][j] = obstacleGrid[i][j-1]
                    elif j-1 < 0 and i-1 >= 0:
                        obstacleGrid[i][j] = obstacleGrid[i-1][j]
                    else:
                        obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
        answer = obstacleGrid[m-1][n-1]
        return answer

# 1st - Wrong Answer
# def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
#     total = self.uniquePaths(len(obstacleGrid), len(obstacleGrid[0]))
#     obstacle_x, obstacle_y = 0, 0
#     for i in range(0, len(obstacleGrid)):
#         for j in range(0, len(obstacleGrid[0])):
#             if obstacleGrid[i][j] == 1:
#                 obstacle_x = i
#                 obstacle_y = j
#                 break
#     obstacle_1 = self.uniquePaths(obstacle_x + 1, obstacle_y + 1)
#     obstacle_2 = self.uniquePaths(len(obstacleGrid) - obstacle_x, len(obstacleGrid[0]) - obstacle_y)
#     answer = total - (obstacle_1 * obstacle_2)
#
#     return answer

#     Input:[[0]]
#     0 하나나 한줄 짜리 배열에 대한 생각 못함
#     해당 조건에 대한 조건문 생성

# 2nd - Wrong Answer
# def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
#     if len(obstacleGrid) == 1 or len(obstacleGrid[0]) == 1:
#         for i in range(0, obstacleGrid[0])
#         if 1 in obstacleGrid or 1 in obstacleGrid[0]:
#             return 0
#         else:
#             return 1
#     total = self.uniquePaths(len(obstacleGrid),len(obstacleGrid[0]))
#     obstacle = False
#     obstacle_x, obstacle_y = 0, 0
#     for i in range(0, len(obstacleGrid)):
#         for j in range(0, len(obstacleGrid[0])):
#             if obstacleGrid[i][j] == 1:
#                 obstacle = True
#                 obstacle_x = i
#                 obstacle_y = j
#                 break
#     if obstacle:
#         obstacle_1 = self.uniquePaths(obstacle_x+1, obstacle_y+1)
#         obstacle_2 = self.uniquePaths(len(obstacleGrid)-obstacle_x, len(obstacleGrid[0])-obstacle_y)
#         answer = total - (obstacle_1 * obstacle_2)
#     else:
#         answer = total
#     return answer

#     Input:[[0, 1], [1, 0]]
#     장애물이 2개 이상이 될 수 있다는 것을 생각 못함
#     심지어 한 줄짜리 배열 처리 조건문도 잘못 작성
#     새로운 방식으로 접근 필요해 전체성 코드 새로 작성

 

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

Unique Paths II - LeetCode

Github : https://github.com/kkkkang1009/leetcode/blob/master/leetcode_63.py

GitHub - kkkkang1009/leetcode: leetcode