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

문제 풀이

프로그래머스 등굣길 문제입니다. 문제 출처

(1) 문제 파악

최단 경로의 개수를 구하는 문제입니다.

(2) 문제 풀이 방법 생각하기

최단 경로 문제이며, 이동은 오른쪽 혹은 아래쪽으로 가능하니 DP를 활용해서 풀 수 있을 것 같은데요! 점화식은

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

로 세웠습니다.

여기서 주의할 점은 물 웅덩이의 좌표가 (m, n)으로 주어진다는 것입니다! (평소처럼 n,m 순서라고 생각했다가 10분동안 멍했네요..ㅎㅎ)

기본적으로 최단 경로의 개수를 구할 때에는 1열과 1행을 모두 1로 만들어놓고 점화식을 수행하는데요. 여기서는 물 웅덩이가 중간에 있을 수 있기 때문에 dp를 수행하기 전에 물 웅덩이 확인을 먼저 해줬습니다.

(4) 구현

class Solution {
    
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n+1][m+1];
        final int MOD = 1_000_000_007;
        
        for(int i=1; i<=m; i++) {
            dp[1][i] = 1;
        }
        
        for(int i=1; i<=n; i++) {
            dp[i][1] = 1;
        }
        
        for(int[] p:puddles) {
            if(p[0] == 1) {
                for(int i=p[1]; i<=n; i++) {
                    dp[i][1] = 0;
                }
            } else if(p[1] == 1) {
                for(int i=p[0]; i<=m; i++) {
                    dp[1][i] = 0;
                }
            } else {
                dp[p[1]][p[0]] = -1;
            }
        }
        
        for(int i=2;i<=n;i++) {
            for(int j=2; j<=m; j++) {
                if(dp[i][j] == -1) {
                    dp[i][j] = 0;
                    continue;
                } 
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD;
            }
        }
        return dp[n][m]%MOD;
    }
}