[LeetCode] Unique Paths II

leetcode.com/problems/unique-paths-ii/

Unique Paths II - LeetCode

2021-01-17

---

public class SolutionUniquePaths2 {
 
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int N = obstacleGrid.length;
        int M = obstacleGrid[0].length;
 
        int dp[][] = new int[N][M];
 
        if(obstacleGrid[0][0] == 0) dp[0][0] = 1; 
        
        for(int i = 1; i < N; i++) 
            if(obstacleGrid[i][0] == 0) dp[i][0] = dp[i-1][0];
        
        for(int i = 1; i < M; i++) 
            if(obstacleGrid[0][i] == 0) dp[0][i] = dp[0][i-1];
        
        
        for(int i = 1; i < N; i++) {
            for(int j = 1; j < M; j++) {
                if(obstacleGrid[i][j] == 0) dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
         
        return dp[N-1][M-1];
    }
    
    public static void main(String[] args) {
        /*int o[][] = {
            {0,0,0},
            {0,1,0},
            {0,0,0}    
        };
        */
        int o[][] = {
                {1,0},
        };
        
        System.out.println(uniquePathsWithObstacles(o));
    }
}
 

#문제풀이
1. dp 배열을 만든다 

2. 시작 위치 (0, 0)이 0인 경우 dp값을 1로 저장한다.

3. y값이 0인 맨 위에 칼럼과, x 값이 0인 맨 왼쪽 세로 컬럼 두 개를 초기화한다.
만약 그 자리에 장애물이 없다면 그 전의 값을 받는다.

4. (1, 1)부터 (N-1, M-1)까지 돌면서, 장애물이 아닌 경우 그 전의 왼쪽값과 위의 값의 합을 더해서 dp배열에 저장한다.

 

5. dp[N-1][M-1] 값을 리턴한다.