[LeetCode] 63. Unique Paths II

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

Unique Paths II - LeetCode

문제 유형 : 동적 계획법(다이나믹 프로그래밍)

문제 난이도 : Medium

 

문제

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 * 10^9.

 

로봇이 [0][0]부터 [m-1][n-1]까지 도달해야 합니다. 

obstaclesGrid 2차원 배열에는 1이 장애물, 0이 다닐 수 있는 빈 공간입니다.

 

 

풀이

i, j칸에 오는 경우의 수를 저장하는 테이블 dp를 만듭니다.

 

0행과 0열은 한줄로 쭉 가는 경우의 수밖에 없으므로, 장애물을 발견하기 전까지는 dp 테이블에1로 설정해줍니다.

장애물을 만나면, 그 뒤로는 닿을 수 없으므로, 경우의 수를 0으로 저장합니다.

 

1행 1열부터 m행 n열까지는 장애물이 아닌 공간인 경우 자신의 윗칸와 자신의 왼쪽 옆칸까지 오는 경우의 수를 합칩니다.

칸에 도달하려면 왼쪽으로부터 또는 위쪽으로부터 오는 경우밖에 없기 때문입니다.

 

마지막 dp[m-1][n-1]에는 [m-1][n-1]까지오는 경우의 수가 저장되므로 반환하면 됩니다.

 

코드

C++

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        const int m = obstacleGrid.size();
        const int n = obstacleGrid[0].size();

        vector<vector<int>> dp (m, vector<int>(n, 0));

        for(int i = 0; i < m; i++) {
            if(obstacleGrid[i][0] == 1) {
                dp[i][0] = 0;
                break;
            } else {
                dp[i][0] = 1;
            }
        }
        for(int i = 0; i < n; i++) {
            if(obstacleGrid[0][i] == 1) {
                dp[0][i] = 0;
                break;
            } else {
                dp[0][i] = 1;
            }
        }

        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }

        return dp[m-1][n-1];
    }
};

 

Python3

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

        for i in range(m):
            if obstacleGrid[i][0] == 1:
                break
            dp[i][0] = 1

        for i in range(n):
            if obstacleGrid[0][i] == 1:
                break
            dp[0][i] = 1

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

        return dp[-1][-1]

 

Dart

class Solution {
  int uniquePathsWithObstacles(List<List<int>> obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    List<List<int>> dp = List.generate(m, (i) => List<int>.filled(n, 0));

    for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++)
      dp[i][0] = 1;

    for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++)
      dp[0][i] = 1;

    for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
        if (obstacleGrid[i][j] == 0) {
          dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
      }
    }

    return dp[m-1][n-1];

  }
}

 

Java

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++)
            dp[i][0] = 1;

        for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++)
            dp[0][i] = 1;

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }

        return dp[m-1][n-1];
    }
}

 

swift

class Solution {
    func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
        let m = obstacleGrid.count
        let n = obstacleGrid[0].count
        var dp = Array(repeating: Array(repeating: 0, count: n), count: m)

        for i in 0..<m {
            if obstacleGrid[i][0] == 1 {
                break
            }
            dp[i][0] = 1
        }

        for i in 0..<n {
            if obstacleGrid[0][i] == 1 {
                break
            }
            dp[0][i] = 1
        }

        for i in 1..<m {
            for j in 1..<n {
                if obstacleGrid[i][j] == 0 {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                }
            }
        }
    return dp[m-1][n-1]
    }
}