99클럽 TIL (240831)

> [Middler] Unique Path 2

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

 

문제 풀이 과정

• DP (동적 계획법)
• 어제 풀었던 Unique path 문제에서 장애물이 추가된 문제이다.
• 목표 : 로봇의 위치에서 그리드의 맨 우측 하단 위치로 가는 경로의 개수

접근 방법

• dp[i][j] = dp[i-1][j] + dp[i][j-1]
• 이때, obstacleGrid[i][j] == 1 이면 갈수 없으므로 0
• ✨ 로봇의 위치에 장애물이 있을 수도 있다는 점을 감안해야한다. 이부분 때문에 한번 실패함.

 

문제 풀이

python

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

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

 

오늘의 회고 및 느낀점

문제를 ....꼼꼼히 읽어라!!!!!