DP2D: 63. Unique Paths II

63. Unique Paths II

 

 

https://youtu.be/d3UOz7zdE4I?si=HXkXE8KW1a0v6Ed5

 

# Time: O(N*M), Space: O(N*M)

from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
    	"""
        # Time: O(N*M), Space:  O(N*M)
        """
        # 격자의 행(M)과 열(N) 개수를 계산
        M, N = len(obstacleGrid), len(obstacleGrid[0])

        # 출발점이 장애물인 경우, 즉시 0 반환
        if obstacleGrid[0][0] == 1:
            return 0

        # 메모이제이션을 위한 딕셔너리 초기화
        dp = {}

        # DFS 탐색 함수 정의
        def dfs(r, c):
            # 격자 바깥으로 나가거나 장애물에 도달한 경우 0 반환
            if r >= M or c >= N or obstacleGrid[r][c] == 1:
                return 0
            
            # 도착점에 도달하면 1 반환
            if r == M - 1 and c == N - 1:
                return 1
            
            # 이미 계산된 경로 수가 있다면 캐시된 값 반환
            if (r, c) in dp:
                return dp[(r, c)]
            
            # 오른쪽과 아래쪽으로 이동하며 가능한 경로 수를 계산
            dp[(r, c)] = dfs(r + 1, c) + dfs(r, c + 1)
            return dp[(r, c)]

        # (0, 0)에서 시작하여 전체 경로 수를 계산
        return dfs(0, 0)

 

코드 설명

1. 격자 크기 정의:
   • M은 격자의 행(row) 개수, N은 열(column) 개수를 정의합니다.
2. 출발점 장애물 확인:
   • obstacleGrid[0][0]이 장애물(1)일 경우 경로가 없으므로 즉시 0을 반환합니다.
3. 메모이제이션 (dp):
   • 이미 계산된 결과를 저장하기 위해 dp 딕셔너리를 사용합니다.
4. DFS 탐색:
   • 각 셀에서 오른쪽과 아래쪽으로 이동 가능한 경로를 탐색합니다.
   • 장애물이나 격자 범위 밖으로 나가면 0을 반환합니다.
   • 도착점에 도달하면 1을 반환합니다.
5. 재귀 호출 및 메모이제이션 활용:
   • (r, c) 위치에서 가능한 경로를 계산하고 결과를 dp에 저장하여 중복 계산을 방지합니다.

1.  

---

동작 방식

1. DFS 탐색:
   • (r, c)에서 오른쪽과 아래로 이동 가능한 모든 경로를 탐색합니다.
2. 장애물 확인:
   • 장애물이 있는 경우 해당 경로는 유효하지 않으므로 0을 반환합니다.
3. 메모이제이션:
   • 계산된 경로 수를 dp에 저장하여 중복 계산을 방지합니다.
4. 도착점 조건:
   • 도착점 (M-1, N-1)에 도달하면 경로를 1로 반환합니다.

 

# Time: O(N*M), Space: O(N)

 

from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # Time: O(N*M), Space: O(N)

        # 격자의 행(M)과 열(N) 개수를 계산
        M, N = len(obstacleGrid), len(obstacleGrid[0])

        # dp 배열 초기화: 각 열의 상태를 저장하는 1차원 배열
        dp = [0] * N
        dp[N-1] = 1  # 도착점에서의 경로는 1로 초기화 (도착점 자체에서 경로 수는 항상 1)

        # 뒤에서부터 각 행을 순회
        for r in reversed(range(M)):
            # 뒤에서부터 각 열을 순회
            for c in reversed(range(N)):
                # 현재 위치에 장애물이 있는 경우 경로 수는 0
                if obstacleGrid[r][c]:
                    dp[c] = 0
                # 그렇지 않은 경우, 현재 위치의 경로는
                # 아래 방향(dp[c]) + 오른쪽 방향(dp[c+1])의 합
                elif c + 1 < N:  # 오른쪽 셀이 격자 범위 내에 있는 경우
                    dp[c] = dp[c] + dp[c+1]
        # dp[0]은 시작점에서 도착점까지의 모든 경로 수를 저장
        return dp[0]

 

코드 동작 원리

1. 1차원 dp 배열:
   • 격자의 경로 수를 저장하기 위해 O(N) 공간 복잡도를 가지는 1차원 배열 dp를 사용합니다.
   • 각 행을 처리할 때, 현재 행의 정보로 dp 배열을 업데이트하여 이전 행의 경로 수를 계산합니다.
2. 도착점 초기화:
   • dp[N-1] = 1: 마지막 열의 도착점에서의 경로 수는 1로 초기화합니다. 이는 도착점에서 시작했을 때 가능한 경로가 하나이기 때문입니다.
3. 뒤에서부터 행, 열 순회:
   • 행: 아래쪽에서 위쪽으로 순회합니다. (reversed(range(M)))
   • 열: 오른쪽에서 왼쪽으로 순회합니다. (reversed(range(N)))
4. 장애물 처리:
   • obstacleGrid[r][c]가 1이면 장애물이므로 dp[c] = 0으로 설정하여 해당 위치에서의 경로를 차단합니다.
5. 경로 계산:
   • 현재 위치의 경로는 아래 방향(dp[c]) + 오른쪽 방향(dp[c+1]) 경로의 합으로 계산합니다.
   • 오른쪽 방향(dp[c+1])은 열 범위를 초과하지 않는 경우에만 더합니다.
6. 결과 반환:
   • 모든 계산이 끝난 후, dp[0]에는 시작점에서 도착점까지의 경로 수가 저장됩니다.

 

이제 한번에 품

 

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # 장애물 있으면 못감
        R, C = len(obstacleGrid), len(obstacleGrid[0])

        # 시작점 또는 도작점에 장애물이 있으면, 못감
        if obstacleGrid[0][0] == 1 or obstacleGrid[R-1][C-1] == 1: 
            return 0

        grid = [[0] * C for _ in range(R)]

        for r in range(R):
            if obstacleGrid[r][0] == 1:
                # 장애물이 있으면, 이것부터 못가니깐. 
                # 0으로 세팅하고 끝냄
                break
            else:
                # 아니면, 1로 초기화
                grid[r][0] = 1

        for c in range(C):
            if obstacleGrid[0][c] == 1:
                # 장애물이 있으면, 이것부터 못가니깐. 
                # 0으로 세팅하고 끝냄
                break
            else:
                # 아니면, 1로 초기화
                grid[0][c] = 1

        for r in range(1, R):
            for c in range(1, C):
                if obstacleGrid[r][c] == 0:
                    if obstacleGrid[r-1][c] == 1:
                        grid[r][c] = grid[r][c-1]
                    elif obstacleGrid[r][c-1] == 1:
                        grid[r][c] = grid[r-1][c]
                    elif obstacleGrid[r-1][c] == 1 and obstacleGrid[r][c-1] == 1:
                        grid[r][c] = 0
                    else:
                        grid[r][c] = grid[r][c-1]+grid[r-1][c]

        return grid[R-1][C-1]

 

• 시간 복잡도: O(R×C)
• 공간 복잡도: O(R×C)

좀더 최적화

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if obstacleGrid[0][0] or obstacleGrid[-1][-1]: # 처음 또는 끝에 장애물이 있으면
            return 0

        ROWS, COLS = len(obstacleGrid), len(obstacleGrid[0])

        dp = [[0]*COLS for _ in range(ROWS)]

        for r in range(ROWS):
            if obstacleGrid[r][0]: # 1 이면
                break # 더이상 못감
            dp[r][0] = 1
        for c in range(COLS):
            if obstacleGrid[0][c]: # 1 이면
                break # 더이상 못감
            dp[0][c] = 1            

        for r in range(1, ROWS):
            for c in range(1, COLS):
                if obstacleGrid[r][c] == 0:
                    dp[r][c] += dp[r-1][c] if not obstacleGrid[r-1][c] else 0
                    dp[r][c] += dp[r][c-1] if not obstacleGrid[r][c-1] else 0

        return dp[-1][-1]