LeetCode Unique Paths ll (JavaScript), DP

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

문제 설명

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 * 109.

Example 1:

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:

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.

---

문제 풀이

1. DFS 로 접근 (실패, 시간 초과)

접근 방식

- (0, 0)부터 시작해 배열의 끝에 도달했을 경우 answer을 1씩 증가 시켜주도록 로직을 작성 (dfs)

- 배열의 길이가 길어지면 시간 초과 오류가 발생

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    let answer = 0;

    if (obstacleGrid[0][0] === 1) {
        return 0;
    }

    let move = [[0, 1], [1, 0]];

    const dfs = (x, y) => {
        if (x === obstacleGrid[0].length - 1 && y === obstacleGrid.length - 1) {
            answer++;
            return;
        }

        for (let i = 0; i < move.length; i++) {
            const mx = x + move[i][0];
            const my = y + move[i][1];

            if (mx < obstacleGrid[0].length && my < obstacleGrid.length && obstacleGrid[my][mx] === 0) {
                dfs(mx, my);
            }
        }
    }

    dfs(0, 0);
    return answer;
};

 

2. DP로 접근 (성공)

접근 방식

- 오른쪽, 아래로만 이동이 가능하므로 특정 위치에서 올 수 있는 경우의 수는 왼쪽, 위에서 오는 경우를 합한 값임

- 즉, 특정 위치에서 왼쪽의 경우의 수 + 위쪽 경우의 수를 합한 값이 현재 위치에서 올 수 있는 경우의 수이다.

- 단, 1씩 더하게되면 장애물이 1을 나타내므로 로직에 잘못된 판단이 될 수 있어. 경우의 수는 2씩 더하고, 최종적으로 2를 나눈 값이 끝지점에 도달할 수 있는 모든 경우의 수를 의미한다.

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    if (obstacleGrid[0][0] === 1) {
        return 0;
    }
    
    let before = [[-1, 0], [0, -1]]; // 왼쪽, 위

    for (let y = 0; y < obstacleGrid.length; y++) {
        for (let x = 0; x < obstacleGrid[0].length; x++) {
            if (x === 0 && y === 0) {
                obstacleGrid[0][0] = 2;
                continue;
            }

            if (obstacleGrid[y][x] === 1) {
                continue;
            }

            for (let i = 0; i < before.length; i++) {
                const bx = x + before[i][0];
                const by = y + before[i][1];

                if (bx >= 0 && by >= 0 && obstacleGrid[by][bx] !== 1) {
                    obstacleGrid[y][x] += obstacleGrid[by][bx];
                }
            }
        }
    }

    return Math.floor(obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] / 2);
};

 

3. DP 개선 (성공)

접근 방식

- 2번째와 유사하게 특정 위치의 경우의 수는 왼쪽, 위쪽의 경우를 더한 값을 의미

- for문 안에 반복문 제거하여 더 깔끔하게 로직 작성

- 반복문 설명

1. x, y =>  0 인 경우 처음 위치를 나타내므로 1로 치환
2. 특정 위치가 1인 경우 장애물이므로 0으로 치환
   • 0으로 치환하는 이유는 다음 값에서 해당 위치를 읽어 더해야 하기 때문
3. y가 0인 경우 -> x기준 왼쪽에서 오는 경로만 계산하면 됨
4. x가 0인 경우 -> y기준 위쪽에서 오는 경로만 계산하면 됨
5. (3, 4)가 아닌 경우 -> 왼쪽, 위에서 오는 경로를 합해주면 됨

- 최종적으로 배열의 끝을 리턴해주면 됨.

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    const [rows, cols] = [obstacleGrid[0].length, obstacleGrid.length];
    if (obstacleGrid[0][0] || obstacleGrid[cols - 1][rows - 1]) {
        return 0;
    }

    for (let y = 0; y < cols; y++) {
        for (let x = 0; x < rows; x++) {
            if (x === 0 && y === 0) {
                obstacleGrid[y][x] = 1;
                continue;
            }

            if (obstacleGrid[y][x] === 1) {
                obstacleGrid[y][x] = 0;
                continue;
            }

            if (y === 0) {
                obstacleGrid[y][x] = obstacleGrid[y][x - 1];
                continue;
            }

            if (x === 0) {
                obstacleGrid[y][x] = obstacleGrid[y - 1][x];
                continue;
            }

            obstacleGrid[y][x] = obstacleGrid[y - 1][x] + obstacleGrid[y][x - 1];
        }
    }

    return obstacleGrid[cols - 1][rows - 1];
};

---

결론

모든 경로를 계산하기 위해 가장 쉬운 방법은 dfs를 이용하는 것이지만, 이는 시간 초과 오류가 발생할 수 있다.

따라서, 특정 위치의 경로를 어떻게 계산하는지 DP형태의 문제로 접근을 해서 해결해야 한다.