DP - 등굣길

프로그래머스(DP) - 등굣길

해당문제는 해당 좌표로 올 수 있는 경우의 수 dp(x,y) = dp(x-1, y) + dp(x, y-1)로 나타 낼 수 있습니다. 이 중 제한 사항인 물이 잠긴 지역으로 갈 수 있는 방법은 0이라 생각하고 계산을 하는 방식으로 진행했습니다.
입력 받은 2차원 배열 puddles에서 해당 puddle 좌표를 구해 물이 잠긴 지역을 표시하고 계산을 진행 하는 중에 물이 잠긴 지역인 경우 계산 없이 0으로 값을 셋팅했습니다. 계산 후 1,000,000,007을 한 이유는 문제 결과로 해당 숫자로 나눈 나머지를 return 하라고 했었고, 계산값이 int의 max value를 넘는 경우도 있을 것으로 보이기에 그렇게 구현하였습니다.(프로그래머스에서 마지막 dp[m][n] 만 DIVISION_NUMBER로 나눌 경우 효율성 테스트를 통과 못함)

private static final int DIVISION_NUMBER = 1000000007;

    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[m+1][n+1];
        boolean[][] puddlesFlag = new boolean[m+1][n+1];

        for (int[] puddle : puddles) {
            puddlesFlag[puddle[0]][puddle[1]] = true;
        }

        dp[1][1] = 1;

        for (int width = 1; width <=m; width++) {
            for (int height = 1; height <= n; height++) {
                if((width == 1 && height == 1)) {
                    continue;
                }

                if (puddlesFlag[width][height]) {
                    dp[width][height] = 0;
                    continue;
                }

                int dpWidth = width - 1;
                int dpHeight = height - 1;

                dp[width][height] = (dp[dpWidth][height] + dp[width][dpHeight]) % DIVISION_NUMBER;
            }
        }

        return dp[m][n];
    }