[프로그래머스] 등굣길 (Java)

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

코딩테스트 연습 - 등굣길

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp=new int[n+1][m+1];
        boolean[][] isPuddles=new boolean[n+1][m+1];
        for (int i=0; i<puddles.length; i++){
            int x=puddles[i][0];
            int y=puddles[i][1];
            isPuddles[y][x]=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 (isPuddles[i][j]) continue;
                dp[i][j]=(dp[i][j-1]%1000000007)+(dp[i-1][j]%1000000007);
            }
        }
        return dp[n][m]%1000000007;
    }
}

문제의 조건을 보면, 위에서 오기, 왼쪽에서 오기만 가능하다. 즉 출발점에서 (i,j)까지 오는 가능한 경로의 수는 그 전 (i-1,j), (i, j-1) 까지의 경로의 수을 더한 값이다. dp[i][j]=dp[i][j-1]+dp[i-1][j] 라는 점화식을 얻을 수 있다.

출발지, 웅덩이인 경우 값을 더하지 않는다.

 

나는 IsPuddles라는 배열을 만들어서 웅덩이 여부를 표시해줬는데, dp 배열에 웅덩이의 위치를 -1로 표시해서, 만약 -1 값을 만났을 때 0으로 바꾸는 식으로 진행해도 된다.