LeetCode - Unique Paths 2

문제 설명

배열이 주어진다.
1은 갈수 없고
0은 갈수 있는 도로이다.
시작은 0,0에서 시작해서 m-1,n-1에서 끝이난다.

위와같은 배열이 주어질때 0,0에서 m-1,n-1 까지 도달할 수 있는 경로의 총 개수를 찾아라.

해결방법

Dynamic Programming을 써야 겠다는 생각이 들었다.
왜냐하면 이전 경로가 다음 경로에 반영이 되니까

이건 고등학교 경로수 구하기 문제니까 더이상 자세한 설명은 생략

코드

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int[][] check = new int[obstacleGrid.length][obstacleGrid[0].length];
        for(int i=0; i<obstacleGrid.length; i++){
            for(int j=0; j<obstacleGrid[i].length; j++){
                if(obstacleGrid[i][j]==1){
                    check[i][j]=0;
                    continue;
                }
                if(i==0&&j==0) check[i][j] = 1;
                else if (i==0) check[i][j] = check[i][j-1];
                else if (j==0) check[i][j] = check[i-1][j];
                else{
                    check[i][j] = check[i-1][j]+check[i][j-1];
                }
            }
        }
        return check[check.length-1][check[0].length-1];
    }
}

해결

몇가지 예외 사항이 있었는데,
Leet Code는 이게 바로 뜨는데 실제 Programmers에서는 그 예외가 어떠한 것인지 안뜨니까,
예외상황에서 더 신경을 써야 될 것 같다.

풀이시간은 14분