[Programmers:DP] 등굣길

❓문제

물 웅덩이를 피해 집에서 학교까지 갈 수 있는 최단 경로의 개수

---

🖐️손코딩

물 웅덩이의 위치 : boolean puddle[][]에 넣기
DP : 해당 칸까지 도달할 수 있는 최단 경로의 개수

for(1~i)
	for(1~j)
    	i==1, j==1 일 때는 왼쪽 값, 위쪽 값 그대로 복사
        물웅덩이가 true 일 때는 continue
        그 외에는 왼쪽값 + 위쪽값 더한값 (파스칼 삼각형)

---

👩‍💻구현 코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int[][] dp = new int[n+1][m+1];
        boolean[][] puddle = new boolean[n+1][m+1];
        
        for(int i = 0; i<puddles.length; i++){
            int a = puddles[i][0];
            int b = puddles[i][1];
            
            puddle[b][a] = true;
        }
        
        dp[1][1] = 1;
        
        for(int i = 1; i<=n; i++){
            for(int j = 1; j<=m; j++){
                
                if(i == 1 && j == 1){
                    continue;
                }
                
                if(puddle[i][j]){
                    continue;
                }
                
                if(i == 1){
                    dp[i][j] = dp[i][j-1];
                } else if(j == 1){
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
                }
                
            }
        }
        
        answer = dp[n][m];
        
        return answer;
    }
}

---

https://school.programmers.co.kr/learn/courses/30/lessons/42898