[프로그래머스 알고리즘 고득점 Kit][동적계획법(Dynamic Programming))][Java] 등굣길

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

프로그래머스

현재 서 있는 곳으로 올 수 있는 방법은
1. 왼쪽에서 오른쪽으로 한칸(numOfShortestPath[x-1][y])
2. 위쪽에서 아래쪽으로 한칸(numOfShortestPath[x][y-1])
2개의 합이 현재 서 있는 곳으로 올 수 있는 경우의 수

중간 block 된 곳은 continue

이 방법을 시작 점 부터 하나씩 채워나간다.

class Solution {
    
    final int MOD = 1_000_000_007;
    
    public int solution(int m, int n, int[][] puddles) {
        long[][] numOfShortestPath = new long[m+1][n+1];
        boolean[][] blocked = new boolean[m+1][n+1];
        for(int[] p : puddles){
            blocked[p[0]][p[1]] = true;
        }
        numOfShortestPath[1][1] = 1;
        for(int x=1; x<=m; x++){
            for(int y=1; y<=n; y++){
                if(x==1 && y==1) continue;
                if(blocked[x][y]) continue;
                
                numOfShortestPath[x][y] = (numOfShortestPath[x-1][y] + numOfShortestPath[x][y-1])%MOD;
            }
        }
        return (int)numOfShortestPath[m][n];
    }
}