[JAVA] 프로그래머스 LEVEL3 보행자 천국

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

프로그래머스

코딩테스트 연습 > 2017 카카오코드 예선 > 보행자 천국

 

난이도: LEVEL3

알고리즘 유형: 다이나믹 프로그래밍 (DP)

문제 풀이

LEVEL3 치고는 난이도가 낮은 문제이다.

자동차는 왼쪽 → 오른쪽 / 위 → 아래 2가지 방법으로만 이동이 가능하다. 

 

또한 해당 구역의 숫자가 1이면 이동 불가능 2면 이동했던 방향으로만 다음 장소로 이동이 가능하다.  

EX) 왼쪽 → 오른쪽 다음 이동도 왼쪽 → 오른쪽

 

이를 3차원 배열로 기록했다.

특정 좌표 x, y의 왼쪽에서 온 경우의 수를 [x][y][0] 기록 위에서 내려온 경우의 수를 [x][y][1]에 기록한다. 

 

indexOutOfRange 검사를 위해 

항상 하던 방식으로 validation 메소드를 만들어 검사한다. 

 

그리고 숫자 커질 수 있으니 문제에서 주어진 숫자로 나누어 나머지를 기록한다. 

 

꿀팁

시작 장소를 cityMap에서 2로 바꾼다. 

cityMap[0][0] = 2

바로 아래인 [1][0][1] = 1

바로 오른쪽 [0][1][0] = 1 

이렇게 만들어지도록 한다. 

꼭 이렇게 안 하고 전 좌표가 0,0 이면 합쳐서 더하는 게 아닌 1만 더하는 방식으로 로직을 짜도 괜찮다. 

정답 코드

class Solution {
    int MOD = 20170805;
    static int N, M; // 행, 열 
    static int [] arx = {0, -1}; // 왼쪽 아래 
    static int [] ary = {-1, 0};
    public int solution(int m, int n, int[][] cityMap) {
        N = m;
        M = n;
        // 0: 왼쪽에서 온 경우의 수 // 1: 위에서 온 경우의 수 
        int [][][] dp = new int [N][M][2];
        dp[0][0][0] = 1;
        dp[0][0][1] = 1;
        cityMap[0][0] = 2;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(cityMap[i][j] == 1) continue;
                for(int k = 0; k < 2; k++){
                    int nx = i + arx[k];
                    int ny = j + ary[k];
                    if(!validation(nx, ny) || cityMap[nx][ny] == 1) continue;
                    if(cityMap[nx][ny] == 2){ // 2
                        dp[i][j][k] += dp[nx][ny][k];
                    }
                    else{
                        dp[i][j][k] += dp[nx][ny][0] + dp[nx][ny][1];
                    }
                    dp[i][j][k] %= MOD;
                }
            }
        }
        return (dp[N-1][M-1][0] + dp[N-1][M-1][1]) % MOD;
    }
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < N && ny < M) return true;
        return false;
    }
}