🔍 Problem

프로그래머스 - 등굣길

---

📃 Input&Output

---

🌁 문제 배경

가. 문제 설명
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항
격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
물에 잠긴 지역은 0개 이상 10개 이하입니다.
집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

나. 접근 방법
최단경로의 수를 dp식으로 더해준다.
다. 문제 유형
dp

---

📒 수도 코드

가. dp 빈 배열 생성
나. 웅덩이(-1)일 경우 0으로
다. 위에서 첫번째 줄이아니면 아래로 더하기
라. 왼쪽에서 첫번째 줄이아니면 오른쪽으로 더하기

---

💻 Code

import java.util.*;

class Solution {
    public  int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n][];
        for (int i=0; i<n; i++){
            dp[i] = new int[m];
        }
        
        for (int[] a : puddles){
            dp[a[1]-1][a[0]-1] = -1;
        }
        dp[0][0]=1;
        
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                
                if(dp[i][j]==-1){
                    dp[i][j]=0;
                    continue;
                }
                
                if(i!=0){
                    dp[i][j] +=dp[i-1][j] % 1000000007;
                }
                
                if(j!=0){
                    dp[i][j]+=dp[i][j-1] % 1000000007;
                }
            }
            
        }
        
        
            return dp[n-1][m-1] % 1000000007;
    }
}

---

🎸 기타

가. Arrays.equals(arr1, arr2)
두개의 배열 원소값들 전부 같은지 비교

---

🤔 느낀점

DP가 너무 어렵다.