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

dp 문제입니다.
문제의 그림과 정보가 일치하지 않습니다.

문제에서 m*n 크기라 나와 있지만, n*m으로 생각해 풀어야 합니다.

이에 따라, 문제에서 주어지는 puddles의 좌표의 값도 서로 바꿔야 합니다.

 

(1,1)부터 (n,m)까지 우측 또는 아래로만 가는 최단 경로 개수를 구하는 문제입니다.

(최단 경로의 크기를 구하는 것인지 알고 오래 헤맸습니다...)

 

특정 위치를 (i,j)라고 하면 좌측 또는 상단의 위치인 (i, j-1)과 (i-1, j)을 확인해 더해주면 됩니다.

단, 우물의 경우는 무시합니다.

 

[구현 코드]

import java.util.*;

class Solution {
    private static int[][] dp;
    private static int di = 1_000_000_007;

    public static int solution(int m, int n, int[][] puddles) {
        int ans = 0;

        dp = new int[n + 1][m + 1];

        for (int[] puddle : puddles) {
            int px = puddle[1];
            int py = puddle[0];

            dp[px][py] = -1;
        }

        dp[1][1] = 1;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                if (dp[i][j] == -1) continue;
                if (dp[i - 1][j] > 0) dp[i][j] += (dp[i - 1][j]) % di;
                if (dp[i][j - 1] > 0) dp[i][j] += (dp[i][j - 1]) % di;
            }
        }

        ans = dp[n][m];

        return ans % di;
    }
}