LeetCode - 고유 경로 II

문제 설명

m x n 정수 배열 그리드가 제공됩니다. 처음에는 왼쪽 상단 모서리(즉, grid[0 [0])에 로봇이 있습니다. 로봇은 오른쪽 하단 모서리(즉, 그리드[m - 1][n - 1])로 이동하려고 합니다. 로봇은 언제든지 아래 또는 오른쪽으로만 이동할 수 있습니다.

장애물과 공간은 그리드에서 각각 1 또는 0으로 표시됩니다. 로봇이 이동하는 경로에는 장애물인 사각형이 포함될 수 없습니다.

로봇이 오른쪽 하단 모서리에 도달하기 위해 취할 수 있는 가능한 고유 경로의 수를 반환합니다.

답이 2 * 10^9보다 작거나 같도록 테스트 케이스가 생성됩니다.

문제 진술 출처: https://leetcode.com/problems/unique-paths-ii

예 1:

Input: obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3 x 3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

예 2:

Input: obstacleGrid = [[0, 1], [0, 0]]
Output: 1

제약:

- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] is 0 or 1

설명

문제는 이전 블로그 게시물Unique Paths과 유사합니다. 무차별 대입 또는 동적 프로그래밍 접근 방식을 사용하여 해결할 수 있습니다.

그러나 우리가 처리해야 하는 유일한 경우는 경로에 있는 장애물입니다. 셀 [i, j]에 장애물이 있는 경우 다음 셀에 도달할 수 있는 방법이 없습니다.

[i, j + 1]//오른쪽 셀

[i + 1, j]//맨 아래 셀

[i, j] 셀 경로 수를 0으로 표시하면 됩니다. 이는 이 셀에 도달할 수 있는 방법이 없음을 나타냅니다.

동적 프로그래밍

위의 접근 방식을 기반으로,
알고리즘으로 직접 이동해 보겠습니다.

- set m = obstacleGrid.size()
      n = obstacleGrid[0].size()

// if the top-left cell has an obstacle, the robot cannot be placed and
// start moving across the grid. We return 0 in such a case.
- if obstacleGrid[0][0] == 1
  - return 0

// set the number of ways to reach the top-left cell as 1
- obstacleGrid[0][0] = 1

// following loop sets the number of ways to reach any cell in the left-most column.
// if we have an obstacle, mark the number of ways to reach that cell
// and all its bottom-adjacent cells as 0.
- loop for i = 1; i < m; i++
  - if obstacleGrid[i][0] == 0
    - obstacleGrid[i][0] += obstacleGrid[i - 1][0]
  - else
    - obstacleGrid[i][0] = 0
- for end

// following loop sets the number of ways to reach any cell in the top-most row.
// if we have an obstacle, mark the number of ways to reach that cell
// and all its right-adjacent cells as 0.
- loop for j = 1; j < n; j++
  - if obstacleGrid[0][j] == 0
    - obstacleGrid[0][j] += obstacleGrid[0][j - 1]
  - else
    - obstacleGrid[0][j] = 0
- for end

// add the number of ways to reach any cell in the rest of the matrix
- loop for i = 1; i < m; i++
  - loop for j = 1; j < n; j++
    - if obstacleGrid[i][j] == 0
      - obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
    - else
      - obstacleGrid[i][j] = 0
    - if end
  - inner for end
- for end

- return obstacleGrid[m - 1][n - 1]

이 접근법의 시간 복잡도는 O(M * N)이고 공간 복잡도는 O(1)입니다.

C++, Golang, Javascript에서 알고리즘을 확인해 봅시다.

C++ 솔루션

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

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

        obstacleGrid[0][0] = 1;

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

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

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

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

골랑 솔루션

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m, n := len(obstacleGrid), len(obstacleGrid[0])

    if obstacleGrid[0][0] == 1 {
        return 0
    }

    obstacleGrid[0][0] = 1

    for i := 1; i < m; i++ {
        if obstacleGrid[i][0] == 0 {
            obstacleGrid[i][0] += obstacleGrid[i - 1][0]
        } else {
            obstacleGrid[i][0] = 0
        }
    }

    for j := 1; j < n; j++ {
        if obstacleGrid[0][j] == 0 {
            obstacleGrid[0][j] += obstacleGrid[0][j - 1]
        } else {
            obstacleGrid[0][j] = 0
        }
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if obstacleGrid[i][j] == 0 {
                obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
            } else {
                obstacleGrid[i][j] = 0
            }
        }
    }

    return obstacleGrid[m - 1][n - 1]
}

자바스크립트 솔루션

var uniquePathsWithObstacles = function(obstacleGrid) {
    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length;

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

    obstacleGrid[0][0] = 1;

    for(let i = 1; i < m; i++) {
        if(obstacleGrid[i][0] == 0) {
            obstacleGrid[i][0] += obstacleGrid[i - 1][0];
        } else {
            obstacleGrid[i][0] = 0;
        }
    }

    for(let j = 1; j < n; j++) {
        if(obstacleGrid[0][j] == 0) {
            obstacleGrid[0][j] += obstacleGrid[0][j - 1];
        } else {
            obstacleGrid[0][j] = 0;
        }
    }

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

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

예제 1의 알고리즘을 시험 실행해 보겠습니다.

Input: obstacleGrid = [
         [0, 0, 0],
         [0, 1, 0],
         [0, 0, 0]
       ]

Step 1: m = obstacleGrid.size()
          = 3
        n = obstacleGrid[0].size()
          = 3

Step 2: if obstacleGrid[0][0] == 1
           0 == 1
           false

Step 3: obstacleGrid[0][0] = 1
        obstacleGrid = [
          [1, 0, 0],
          [0, 1, 0],
          [0, 0, 0]
        ]

Step 4: loop for i = 1; i < m;
          1 < 3
          true

          if obstacleGrid[i][0] == 0
             obstacleGrid[1][0] == 0
             true

             obstacleGrid[i][0] += obstacleGrid[i - 1][0]
                                 = obstacleGrid[i][0] +  obstacleGrid[i - 1][0]
                                 = obstacleGrid[1][0] + obstacleGrid[0][0]
                                 = 0 + 1
                                 = 1

          i++
          i = 2

          for i < m
          2 < 3
          true

          if obstacleGrid[i][0] == 0
             obstacleGrid[2][0] == 0
             true

             obstacleGrid[i][0] += obstacleGrid[i - 1][0]
                                 = obstacleGrid[i][0] +  obstacleGrid[i - 1][0]
                                 = obstacleGrid[2][0] + obstacleGrid[1][0]
                                 = 0 + 1
                                 = 1

          i++
          i = 3

          for i < m
          3 < 3
          false

        obstacleGrid = [
          [1, 0, 0],
          [1, 1, 0],
          [1, 0, 0]
        ]

Step 5: loop for j = 1; j < n;
          1 < 3
          true

          if obstacleGrid[0][j] == 0
             obstacleGrid[0][1] == 0
             true

             obstacleGrid[0][j] += obstacleGrid[0][j - 1]
                                 = obstacleGrid[0][j] + obstacleGrid[0][j - 1]
                                 = obstacleGrid[0][1] + obstacleGrid[0][0]
                                 = 0 + 1
                                 = 1

          j++
          j = 2

          for j < n
          2 < 3
          true

          if obstacleGrid[0][j] == 0
             obstacleGrid[0][2] == 0
             true

             obstacleGrid[0][j] += obstacleGrid[0][j - 1]
                                 = obstacleGrid[0][j] + obstacleGrid[0][j - 1]
                                 = obstacleGrid[0][2] + obstacleGrid[0][1]
                                 = 0 + 1
                                 = 1

          j++
          j = 3

          for j < n
          3 < 3
          false

        obstacleGrid = [
          [1, 1, 1],
          [1, 1, 0],
          [1, 0, 0]
        ]

Step 6: loop for i = 1; i < m; i++
          loop for j = 1; j < n; j++

            if obstacleGrid[i][j] == 0
               obstacleGrid[1][1] == 0
               1 == 0
               false

            else
               obstacleGrid[i][j] = 0
               obstacleGrid[1][1] = 0

            obstacleGrid = [
              [1, 1, 1],
              [1, 0, 0],
              [1, 0, 0]
            ]

            j++
            j = 2

            for j < n
            2 < 3
            true

            if obstacleGrid[i][j] == 0
               obstacleGrid[1][2] == 0
               true

               obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
                                  = obstacleGrid[1 - 1][2] + obstacleGrid[1][2 - 1]
                                  = obstacleGrid[0][2] + obstacleGrid[1][1]
                                  = 1 + 0
                                  = 1

            obstacleGrid = [
              [1, 1, 1],
              [1, 0, 1],
              [1, 0, 0]
            ]

            j++
            j = 3

            for j < n
            3 < 3
            false

        i++
        i = 2

Step 7: loop for i < m
          2 < 3
          true

          loop for j = 1; j < n; j++

            if obstacleGrid[i][j] == 0
               obstacleGrid[2][1] == 0
               true

               obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
                                  = obstacleGrid[2 - 1][1] + obstacleGrid[2][1 - 1]
                                  = obstacleGrid[1][1] + obstacleGrid[2][0]
                                  = 0 + 1
                                  = 1

            obstacleGrid = [
              [1, 1, 1],
              [1, 0, 1],
              [1, 1, 0]
            ]

            j++
            j = 2

            for j < n
            2 < 3
            true

            if obstacleGrid[i][j] == 0
               obstacleGrid[2][2] == 0
               true

               obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
                                  = obstacleGrid[2 - 1][2] + obstacleGrid[2][2 - 1]
                                  = obstacleGrid[1][2] + obstacleGrid[2][1]
                                  = 1 + 1
                                  = 2

            obstacleGrid = [
              [1, 1, 1],
              [1, 0, 1],
              [1, 1, 2]
            ]

            j++
            j = 3

            for j < n
            3 < 3
            false

        i++
        i = 3

Step 8: loop for i < m
          3 < 3
          false

Step 9: return obstacleGrid[m - 1][n - 1]
               obstacleGrid[3 - 1][3 - 1]
               obstacleGrid[2][2]
               2

We return the answer as 2.