프로그래머스 등굣길 (JAVA)

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

코딩테스트 연습 - 등굣길

 

저는 해당 문제를 DP를 이용하여 문제를 해결하였습니다.

DP를 통해 이전에 계산한 값을 다시 계산하지 않도록 하였습니다.

혹시 런타임에러가 나오신다면 물이 잠긴 지역의 좌표가 (가로,세로) 입니다.
(저는 이것때문에 계속 런타임에러를 일으켰습니다.)

 

import java.util.*;
class Solution {
    private static final int LIMIT = 1_000_000_007;
    private static final int[] DY = {1,0};
    private static final int[] DX = {0,1};
    private static final boolean EMPTY = false;
    private static final boolean WATER = true;
    private static final int NOT_VALID = -1;
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        boolean[][] map = new boolean[n][m];
        int[][] dp = new int[n][m];
        for(int i = 0  ;i < n ; i++){
            Arrays.fill(dp[i], NOT_VALID);
        }
        for(int[] puddle : puddles){
            int y = puddle[1] -1;
            int x = puddle[0] -1;
            map[y][x] = WATER;
        }
        answer = dfs(0,0,n,m,map,dp);
        return answer;
    }
    private int dfs(int y,int x,int n,int m,boolean[][] map,int[][]dp){
        if(y == n-1 && x == m-1){
            return 1;
        }
        if(map[y][x] == WATER){
            return 0;
        }
        if(dp[y][x] != NOT_VALID){
            return dp[y][x];
        }
        int result = 0;
        for(int i = 0 ; i < 2; i++){
            int ny = y + DY[i];
            int nx = x + DX[i];
            if(checkBound(ny,nx,n,m)){
                result += dfs(ny,nx,n,m,map,dp);
                result %= LIMIT;
            }
        }
        dp[y][x] = result;
        return result;
    }
    private boolean checkBound(int y,int x,int n,int m){
        if(y >= 0 && y < n && x >= 0 && x < m){
            return true;
        }
        return false;
    }
}