[99클럽 코테 스터디 41일차 TIL] Unique Paths 2 - Java [자바][LeetCode]

 

📜 문제 내용

 

🤔 과정

• 시작점은 반드시 obstacleGrid[0][0] 이며 도착점은 반드시 최우측 하단이다. 
• Unique Paths 와 다르게 장애물을 고려해서 dp 배열을 구성한다. 

 

✨ 최초 제출 답안 - 🙆‍♂️ 통과

`class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length; // 행 크기
        int n = obstacleGrid[0].length; // 열 크기
        
        // dp 배열 초기화
        int[] dp = new int[n];
        dp[0] = 1; // 시작점 초기화
        
        // dp 배열을 업데이트하면서 최적화된 경로 계산
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0; // 장애물이 있는 경우 경로는 0
                } else if (j > 0) {
                    dp[j] += dp[j - 1]; // 이전 열에서 온 경로 더하기
                }
            }
        }
        
        return dp[n - 1]; // 도착점의 경로 수 반환
    }
}

 

🔗 문제 링크

• LeetCode - Unique Paths 2 (링크)