[프로그래머스] [Level3] 등굣길 JAVA

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

코딩테스트 연습 - 등굣길

문제

풀이

(1,1) 집에서 (m,n)학교 까지 가는데 최단거리로 가는 경우의 수를 구하는 문제이다.
우선 , 문제의 조건으로 오른쪽or아래 만 진행한다고 하였으니 어디로 가든 최단거리는 기본으로 잡고 들어간다.

만약 현지위치를 (x,y) 라고 하면 이 위치에 오기 까지의 경우의수는 (x-1,y) 또는 (x,y-1)의 합이다.
즉 , 현재위치의 경우의 수를 dp[y][x] = dp[y-1][x] + dp[y][x-1] 라는 점화식을 세울 수 있음.

범위체크하고 , 물 웅덩이 있는부분은 패스하면서 진행하면 끝

import java.util.*;
import java.io.*;
import java.util.stream.*;
 
 
public class Main {
 
    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Solution sol = new Solution();
        int[][] arr = {{2,2}};
        sol.solution(4,3,arr);
 
 
    }
}
class Solution {
    int[] dx={1,0},dy={0,1};
    int[][] map,dp;
    public int solution(int m, int n, int[][] puddles) {
        map = new int[n+1][m+1];
        dp = new int[n+1][m+1];
        for (int[] puddle : puddles) map[puddle[1]][puddle[0]] = 1;
        dp[1][1]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                for(int k=0;k<dx.length;k++){
                    int nextX = j+dx[k];
                    int nextY = i+dy[k];
 
                    if(!isRange(nextX,nextY) || map[nextY][nextX]==1) continue;
                    dp[nextY][nextX] += dp[i][j];
                    dp[nextY][nextX] %=1000000007;
                }
            }
        }
        return dp[n][m];
    }
    boolean isRange(int x,int y){
        return x>=1&&y>=1&&x<map[0].length&&y<map.length;
    }
}