[LeetCode] 63. Unique Paths II

이전 풀이와 대부분 동일한 방식으로 진행되며, 첫번째 행과 열을 1로 초기화 하는 것이 아닌 이전 셀들의 값으로 채워넣으므로 써 장애물이 있을 경우에 발생하는 예외를 방지할 수 있다.

장애물이 없이 초기화 된 셀의 경우는 이전과 같이 좌측 셀의 경우의 수 + 상단 셀의 경우의 수
를 계산하여 현재 셀의 경우의 수를 구할 수 있음

😎풀이

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    
    // 시작점에 장애물이 있으면 경로가 없으므로 0을 반환
    if (obstacleGrid[0][0] === 1) return 0;
    
    // dp 배열 초기화
    const dp = Array.from({ length: m }, () => Array(n).fill(0))
    
    // 시작점 설정
    dp[0][0] = 1;
    
    // 첫 번째 행 초기화 (장애물이 있을 경우 이후 셀들도 모두 접근불가)
    for (let j = 1; j < n; j++) {
        if (obstacleGrid[0][j] === 0) {
            dp[0][j] = dp[0][j-1];
        }
    }
    
    // 첫 번째 열 초기화 (장애물이 있을 경우 이후 셀들도 모두 접근불가)
    for (let i = 1; i < m; i++) {
        if (obstacleGrid[i][0] === 0) {
            dp[i][0] = dp[i-1][0];
        }
    }
    
    // 나머지 칸들에 대해 경로 수 계산
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] === 0) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    
    // 마지막 칸의 경로 수 반환
    return dp[m-1][n-1];
}