[LeetCode] 63. Unique Paths II

https://leetcode.com/

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.

 

Example 1:

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

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:

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

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.

 

Code :

var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length; // 그리드의 행 길이
    const n = obstacleGrid[0].length; // 그리드의 열 길이

    if (obstacleGrid[0][0] === 1) {
        return 0; // 시작 지점에 장애물이 있으면 0을 반환
    }

    // dp 배열 초기화
    const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));

    dp[0][0] = 1; // 시작 위치의 경우 1로 설정

    // 첫 번째 열 초기화
    for (let i = 1; i < m; i++) {
        if (obstacleGrid[i][0] === 0) {
            dp[i][0] = dp[i - 1][0]; // 장애물이 없는 경우 이전 값과 같음
        }
    }

    // 첫 번째 행 초기화
    for (let j = 1; j < n; j++) {
        if (obstacleGrid[0][j] === 0) {
            dp[0][j] = dp[0][j - 1]; // 장애물이 없는 경우 이전 값과 같음
        }
    }

    // 그리드의 나머지 부분을 채움
    for (let i = 1; i < m; i++) {
        for (let 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]; // 오른쪽 아래 모서리의 값 반환
};

 

Solutions Code :

var uniquePathsWithObstacles = function(obstacleGrid) {
    // 예외 처리: 그리드가 존재하지 않거나 시작 지점이 장애물인 경우
    if (!obstacleGrid || obstacleGrid[0][0] === 1) {
        return 0;
    }

    const rows = obstacleGrid.length;    // 그리드의 행 수
    const cols = obstacleGrid[0].length; // 그리드의 열 수

    // DP 배열 초기화: 열의 수만큼 0으로 초기화
    const dp = new Array(cols).fill(0);
    dp[0] = 1; // 시작 지점은 1로 초기화 (장애물이 없는 경우에만 이동 가능)

    // 그리드 순회
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (obstacleGrid[r][c] === 1) {
                dp[c] = 0; // 현재 위치에 장애물이 있는 경우, 경로 수 초기화
            } else {
                if (c > 0) {
                    dp[c] += dp[c - 1]; // 왼쪽 값과 현재 위치 값의 합으로 갱신
                }
            }
        }
    }

    return dp[cols - 1]; // 최종 결과는 마지막 열의 값
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode