[JAVA/DP] 등굣길

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

프로그래머스

 

 

 

 

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        
        // 쉽게 하기위해 판 생성
        int[][] board = new int[n+1][m+1];
        board[1][1] = 1;
        // 웅덩이는 -1로 표시
        for(int[] puddle : puddles) {
            // 이거때문에 한참 헤맴... [puddle[0]][puddle[1]]이 아님...
            board[puddle[1]][puddle[0]] = -1;
        }
        
        /*
            최단 경로를 구하는게 아니라,
            최단 경로의 수를 구하는 것이므로,
            우측, 아래로만 움직이며 해당 칸까지 가기 위한 경우의 수를 계산하면 됨.
        */
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(board[i][j] == -1) {
                    // 물웅덩이는 논외
                    continue;
                }
                // 우측, 아래로만 움직임
                if(board[i][j-1] > 0) {
                    board[i][j] += board[i][j-1] % 1000000007;
                }
                if(board[i-1][j] > 0) {
                    board[i][j] += board[i-1][j] % 1000000007;
                }
            }
        }
        
        return board[n][m] % 1000000007;
    }
}