Leetcode Python - 63. Unique Paths II

Leetcode #63 - Unique Paths II

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. matrix을 집중적으로 풀어보겠습니다.

리트코드의 문제 63 ‘Unique Paths II’을 파이썬으로 풀어 보도록 하겠습니다.

포인트는 첫 row와 첫 column을 세팅해주고 (장애물을 만나면 그 뒤의 값들은 방문 할 수 없으므로) 그 이후 나머지 row와 column에 대해 계산을 진행해 나가면 됩니다.

전체 코드는 아래와 같습니다.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        if obstacleGrid[-1][-1]:
            return 0
        # initial setting - column
        for i in range(n):
            if obstacleGrid[0][i]:
                for k in range(i,n):
                    obstacleGrid[0][k] = 0
                break
            else:
                obstacleGrid[0][i] = 1
        # initial setting - row
        for i in range(1,m):
            if obstacleGrid[i][0] or not obstacleGrid[0][0]:
                for k in range(i, m):
                    obstacleGrid[k][0] = 0
                break
            else:
                obstacleGrid[i][0] = 1
        if m == 1 or n ==1 :
            return obstacleGrid[-1][-1]
        # actual calculate
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j]:
                    obstacleGrid[i][j] = 0
                else:
                    obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
        
        return obstacleGrid[-1][-1]

시간복잡도는

• O(m*n) : 모든 element를 방문

공간복잡도는

• O(1) : on place