[프로그래머스,Java] Level3: 보행자 천국

 

 

문제분석:  특수조건을 유의하여 최소거리의 갯수 찾기

 

 

왜 이 문제는 최소거리의 갯수인가?

자동차는 오른쪽 또는 아래로만 갈수있기때문 

위 또는 왼쪽으로 돌아가는 행위는 있을수 없기에, 길이 막히지만 않고 도달한다면 

무조건 최소거리다.

 

 

특수조건:

 

0 :  자유로운 통행가능

1: 통행 금지

2: 커브 금지

 

 

0과 1인 경우는 간단하지만

 

2인 경우때문에 로직이 더 복잡해진다.

커브를 금지한다는뜻은, 이전에 온 방향이 왼쪽에서, 또는 위에서 온것인지 

판별을 해야하기때문이다.

 

 

그래서 거리 방향 판별을 어떻게 할까??

 

3차원 배열을 사용한다.

 

즉, dp[방향][X좌표][Y좌표]   = dp[2][N][N] 

 

거리가 0일땐, 모든 방향을 통과하니  (현재 세로방향DP+ 현재 가로방향DP)을 다음 지역에 더해준다.

 

거리가 1일땐, 통행이 금지니 무시한다.

 

거리가 2일땐, 방향이 다르기때문에  다음과같이넣어야한다.

=> 오른쪽 장소를 갈때 : 현재 가로 방향DP만 더한다.

=> 아래족 장소를 갈때 : 현재 세로 방향DP만 더한다.

즉, 커브의 DP는 무시한다.

 

전체 풀이:

 

class Solution {
    int MOD = 20170805;
    public int solution(int m, int n, int[][] cityMap) {
        int answer = 0;
        // [방향][X거리][Y거리]
        int[][][] dp = new int[2][m+1][n+1];
        
        //문제의 히든? 케이스 
        //무조건 최소거리
        //최소거리 이외의 거리는 없는것이나 마찬가지
        
        
        dp[0][0][0]=1;
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(cityMap[i][j]==0){
                    //가로 진행
                    dp[0][i+1][j]+=(dp[0][i][j]+dp[1][i][j])%MOD;
                    //세로 진행
                    dp[1][i][j+1]+=(dp[0][i][j]+dp[1][i][j])%MOD;
                }
                else if(cityMap[i][j]==2){
                    //가로 진행
                    dp[0][i+1][j]+=dp[0][i][j];
                    dp[0][i+1][j]%=MOD;
                    //세로 진행
                    dp[1][i][j+1]+=dp[1][i][j];
                    dp[1][i][j+1]%=MOD;
                }
            }
        }
        
        return (dp[0][m-1][n-1]+dp[1][m-1][n-1])%MOD;
    }
}