Leetcode - 63. Unique Paths II

문제

장애물이 1, 갈수있는도로가 0으로 주어진다. 좌상단에서 우하단으로 이동할수 있는 모든 경로의 갯수는?

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

아이디어

• 목적지(i, j) 로 갈수 있는 경로는 위에서(i-1, j) 좌측에서(i, j-1) 오는 방법 두가지다. 목적지부터 재귀적으로 반복하면 된다. 경계값일때 리턴값은 0인데 장애물도 경계값과 동일하게 취급하여 0을 리턴한다.
• 유사문제
  Leetcode - 62. Unique Paths

풀이 brute-force

기본적인 재귀 구조

class Solution {
public:
    int size_r = 0;
    int size_c = 0;
    int path(vector<vector<int>>& obt, int i, int j) {
        if (i < 0 || j < 0)
            return 0;
        if (obt[i][j] == 1)
            return 0;
        if (i == 0 && j == 0)
            return 1;
        
        return path(obt, i - 1, j) + path(obt, i, j - 1);
    }
    int uniquePathsWithObstacles(vector<vector<int>>& obt) {
        size_r = obt.size();
        size_c = obt[0].size();
        return path(obt, size_r - 1, size_c - 1);
    }
};

풀이 DP

위에서 memoization 추가

class Solution {
public:
    int size_r = 0;
    int size_c = 0;
    int vis[101][101] = {0};

    int path(vector<vector<int>>& obt, int i, int j) {
        if (i < 0 || j < 0)
            return 0;
        if (obt[i][j] == 1)
            return 0;
        if (i == 0 && j == 0)
            return 1;
        if (vis[i][j])
            return vis[i][j];
        vis[i][j] = path(obt, i - 1, j) + path(obt, i, j - 1);
        return vis[i][j];
        
    }
    int uniquePathsWithObstacles(vector<vector<int>>& obt) {
        size_r = obt.size();
        size_c = obt[0].size();
        return path(obt, size_r - 1, size_c - 1);
    }
};