프로그래머스 보행자 천국 (JAVA)

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

코딩테스트 연습 - 보행자 천국

 

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

각각의 경로로 가는 경로의 수를 구하였고, DP를 이용하여 한번 계산한 곳은 다시 계산하지 않도록 하였습니다.

저는 DP를 dp[y좌표][x좌표][해당 좌표로 어떤 방향으로 왔는지]로 정의하였습니다.

해당 좌표를 어떤 방향으로 왔는지에 따라 경로의 경우의 수가 달라지기 때문에 위와 같이 정의하였습니다.

 

import java.util.*;
class Solution {
    private static int MOD = 20170805;
    private static int[] dy = {1,0};
    private static int[] dx = {0,1};
    private static int GO_STRAIGHT = 2;
    private static int NOT_VALID = -1;
    private static int BLOCK = 1;
    public int solution(int n, int m, int[][] cityMap) {
        int[][][] dp = new int[n][m][2];
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                Arrays.fill(dp[i][j],NOT_VALID);
            }
        }
        int answer = dfs(0,0,0,cityMap,n,m,dp);
        return answer;
    }
    private static int dfs(int y ,int x, int dir,int[][] map,int n,int m,int[][][] dp){
        if(y == n-1 && x == m-1){
            return 1;
        }
        if(dp[y][x][dir] != NOT_VALID){
            return dp[y][x][dir];
        }
        int result = 0;
        for(int i = 0 ; i < 2 ; i++){
            if(map[y][x] == GO_STRAIGHT && i != dir){
                continue;
            }
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(checkBound(ny,nx,n,m) && map[ny][nx] != BLOCK){
                result += dfs(ny,nx,i,map,n,m,dp);
                result %= MOD;
            }
        }
        dp[y][x][dir] = result;
        return result;
    }
    private static boolean checkBound(int y,int x,int n,int m){
        if(y >=0 && y < n && x >= 0 && x < m){
            return true;
        }
        return false;
    }
}