[ 프로그래머스 ] #42898 : 등굣길 - JAVA

🔗 등굣길

🔎 Dynamic Programming

1. 작은 문제를 통해 큰 문제 해결 가능
   • (i, j)의 값을 구하려면 이전 칸들의 값(dp[i-1][j], dp[i][j-1])을 이용하여 구할 수 있음
2. 중복계산 많음
   • dp[i][j]에 최단 경로의 개수를 저장해 재사용
3. 최적 부분 구조
   • 문제의 최적 해가 하위 문제들의 최적 해로 구성될 수 있음
   • (i, j)로 가는 경로의 개수는 (i-1, j)와 (i, j-1)에서의 경로 개수만 알면 구할 수 있음
4. 점화식 기반의 계산
   • 웅덩이인 경우 dp[i][j]=0
   • 나머지 dp[i][j]=dp[i-1][j]+dp[i][j-1]

class Solution {
    static int MOD=1000000007;
    static int[][]dp;
    public int solution(int m, int n, int[][] puddles) {
        // 오른쪽, 아래쪽으로만 이동
        // 최단 경로의 개수 
        dp=new int[n][m];
        for(int[]puddle:puddles){
            dp[puddle[1]-1][puddle[0]-1]=-1;
        }
        int answer = find(dp,puddles);
        return answer;
    }
    public int find(int [][]dp,int [][]puddles){
        dp[0][0]=1;
        for(int i=0;i<dp.length;i++){

            for(int j=0;j<dp[0].length;j++){

                if(i==0&&j==0)continue;

                if(dp[i][j]==-1) {// 웅덩이인 경우
                    dp[i][j] = 0;
                    continue;
                }

                if (i > 0) {// 위에서 오는 경우
                    dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
                }

                if (j > 0) {// 왼쪽에서 오는 경우
                    dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
                }                
            }
        }
        return dp[dp.length-1][dp[0].length-1];
    }

}