(Leet Code JS)Unique Paths II

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

Unique Paths II - LeetCode

 

DP 알고리즘.

Unique Path 문제에서 장애물이 추가된 문제다.

 

m x n 크기로 DP 배열을 선언하여 0으로 초기화한다.

만약 obstacleGrid[0][0]이 1이라면 출발점이 장애물로 막혀있고, 더 이상 진행할 수 없다는 뜻이된다.

그렇다면 0을 바로 리턴하여 종료한다.

 

그렇지 않다면 이중 for문으로 진행.

만약 현재 방문한 좌표가 1이라면 장애물이기 때문에 continue.

나머지 부분은 아래 링크의 설명과 같다.

https://eunchanee.tistory.com/639

(Leet Code JS)Unique Paths

const uniquePathsWithObstacles = (obstacleGrid) => {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const dp = Array.from({length: m}, () => Array(n).fill(0));
    
    if(obstacleGrid[0][0]){
        return 0;
    }
    
    dp[0][0] = 1;
    
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(obstacleGrid[i][j]){
                continue;
            }
            
            if(i === 0){
                if(j === 0){
                    continue;
                } else{
                    dp[i][j] += dp[i][j - 1];
                }
            } else{
                if(j === 0){
                    dp[i][j] += dp[i - 1][j];
                } else{
                    dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
    }
    
    return dp[m - 1][n - 1];
};