등굣길

문제 정보

• 프로그래머스 Lv.3
• DP
• 문제 링크

풀이

최단 경로 경우의 수 문제다.

오른쪽 혹은 아래쪽으로만 이동하므로, (i, j)에 도달하는 최단 경로는 반드시 왼쪽 칸 (i, j - 1) 또는 위쪽 칸 (i - 1, j) 에서만 온다. 따라서 dp[i][j]는 다음과 같다.

• dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

이는 “a → b가 최단이고 b → c가 최단이면 a → c도 최단”이라는 성질을 이용한 것이다.

또한 경로 수가 매우 커질 수 있으므로 매 단계마다 % 1e7을 적용한다.

구현 시 주의할 점은 문제에서 puddles는 [x, y](열, 행) 순서로 주어지는데, DP 테이블은 dp[행][열]로 구성되어 있으므로 dp[puddle[1]][puddle[0]]으로 저장해야 한다.

코드

import java.util.*;
 
class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n + 1][m + 1];
        int MOD = 1_000_000_007;
        
        for(int[] puddle : puddles)
            dp[puddle[1]][puddle[0]] = -1;
        
        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 (dp[i][j] == -1) {
                    dp[i][j] = 0;
                    continue;
                }
                
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD;
            }
        }
        
        return dp[n][m];
    }
}