[LeetCode] Unique Paths II(C++)

문제

Unique Paths II

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.

m x n 정수 배열열이 주어지며 초기에 왼쪽 위 모서리에 로봇이 있습니다. 로봇은 오른쪽 아래 모서리로 이동하려고 한다. 로봇은 아래나 오른쪽으로만 이동이 가능하다.
장애물과 공간이 각각 1 또는 0으로 표시되고 로봇은 장애물이 있는 곳을 가지 못한다.
로봇이 오른쪽 하단 모서리로 갈 수 있는 경로 수를 반환합니다.

해결방법

위의 사진같은 A에서 B를 가는 경로의 수를 구하는 문제를 풀어본 경험이 있을텐데 갈수 있는 경로의 수를 써가며 더해가능 방식으로 해결을 하였는데 그러한 방식을 이 문제에도 그대로 적용하여 해결하면된다.

성공코드

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& g) {
        int m=g.size(); //세로 사이즈
        int n=g[0].size(); //가로 사이즈
        int a[m][n];
        //vector<vector<int>> a(m,vector<int>(n));
        
        if(g[0][0] || g[m-1][n-1] ) return 0; 
        //출발지, 도착지에 장애물이 있으면 0 return
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(g[i][j] != 0) a[i][j] = 0; //장애물이 있으면 
                else if(i==0 && j==0) a[0][0]=1;  //출발지 1로 설정
                //i or j가 0이면 이전칸 까지 가는 경로와 수가 동일함
                else if(i==0) a[0][j]=a[0][j-1];
                else if(j==0) a[i][0]=a[i-1][0];
                //나머지의 경우 왼쪽과 위의 위치까지 도달하는 경로를 합한다.
                else a[i][j] = a[i][j-1] + a[i-1][j];
            }
        }

        return a[m-1][n-1]; //도착지점에 해당하는 경로를 반환
    }
};