[프로그래머스] - 등굣길

등굣길

풀이

이동방향이 아래와 오른쪽밖에 없으므로 현재 위치에서 올 수 있는 방향은 위와 왼쪽 방향에서 오는 것이다. 따라서 현재 위치에 도달하는 방법의 수는 (왼쪽 칸까지 오는 방법의 수) + (위쪽 칸까지 오는 방법의 수) 가 된다.

단, 가장 위쪽 칸의 경우는 왼쪽에서 오는 경로만 고려하고, 가장 왼쪽 칸의 경우에는 위쪽에서 오는 경로만 고려하도록 한다.

코드

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n][m];
        boolean[][] isPuddle = new boolean[n][m];
        
        for(int[] p : puddles){
            isPuddle[p[1] - 1][p[0] - 1] = true;
        }
        dp[0][0] = 1;
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(isPuddle[i][j]){
                    dp[i][j] = 0;
                    continue;
                }
                if(i != 0){
                    dp[i][j] += dp[i - 1][j] % 1000000007;
                }
                if(j != 0){
                    dp[i][j] += dp[i][j - 1] % 1000000007;
                }
                
            }
        }
        
       
        return dp[n - 1][m - 1] % 1000000007;
    }
}