[lv2] 등굣길

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

처음엔 0열과 0행은 모두 한가지 최단 경로밖에 없으므로
다음과 같은 꼴이라고 생각했다. 0열이나 0행에 웅덩이가 있는 경우가 반례였다.

S 1 1 1 1 1

1 0 0 0 0 0

1 0 0 0 0 0

1 0 0 0 0 0

1 0 0 0 0 E

이후 padding을 준 dp로 바꿨다.

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {

        int mod = 1000000007;

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

        dp[1][1] = 1;

        boolean[][] water = new boolean[n+1][m+1];

        for(int i=0; i<puddles.length; i++)
            water[puddles[i][1]][puddles[i][0]] = true;

        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {

                if(water[i][j]) continue;

                if(!water[i-1][j])
                    dp[i][j] += dp[i-1][j];

                if(!water[i][j-1])
                    dp[i][j] += dp[i][j-1];

                dp[i][j] %= mod;
            }
        }

        return dp[n][m];
    }
}