[프로그래머스/java] 42898 등굣길

문제

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

물 웅덩이가 있는 곳을 피해 [1,1]에서 학교인 [N,M]까지 갈 수 있는 최단거리의 개수를 1000000007로 나눈 나머지를 구한다.

풀이

중학교 때 풀었던 길 찾기, 문제 푸는 방법을 생각하면 된다.

• 조건
  오른쪽/아래쪽으로만 움직일 수 있다.
  즉, 특정 위치 (x, y)로 가기 위해서는 (x-1, y) 또는 (x, y-1)에서만 갈 수 있다!
  (x,y) 로 갈 수 있는 최단 거리는 (x-1, y)까지 갈 수 있는 최단 거리 + (x, y-1)까지 갈 수 있는 최단 거리
  dp[x][y] = dp[x-1][y] + dp[x][y-1]

코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int mod = 1000000007;
        
        int[][] route = new int[n][m];
        route[0][0] = 1;
        
        for(int[] puddle : puddles){
            // 물 웅덩이 좌표의 x, y 가 반대로 나와있음
            route[puddle[1]-1][puddle[0]-1] = -1;
        }
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j< m; j++){
                
                if(route[i][j] == -1){
                    route[i][j] = 0;
                    continue;
                }
                
                // dp[x][y] = dp[x-1][y] + dp[x][y-1]
                // 맨 위가 아니라면
                if( i != 0 ){
                    route[i][j] += route[i-1][j] % mod; 
                }
                // 맨 아래가 아니라면
                if( j != 0 ){
                    route[i][j] += route[i][j-1] % mod;
                }
            }
        }
        
        answer = route[n-1][m-1] % mod;
        return answer;
    }
}