프로그래머스 Lv.3) 보행자 천국

2017 카카오코드 예선

보행자 천국

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

풀이

DP 문제임을 눈치 챘고, DP로 풀기위해 노력했다. 하지만, 눈치챈 것 이상도 이하도 아니었다.

DP임을 알고도 어떻게 해야할지 감이 안잡혔기 때문이다.. 처음에는 2차원 배열 DP를 만들어 x축과 y축이 각각 0인 좌표들에 통행 금지 표지판을 만나기 전까지 1을 저장해주었다. (y=0일 때, x를 증가하면서 저장, x=0일 때, y를 증가시키면서 저장)

 

하지만, 나중에 회전 불가 표지판을 만날 때 어떤 경로가 어디서 오는지 파악하지 못하는 경우가 생겼다.

문제의 규칙이 오른쪽 혹은 아래쪽으로만 진행하며 최단 경로를 찾는 것이기 때문에, 오른쪽과 아래쪽을 저장하는 3차원 배열로 만들기로 했다. 

 

어떻게 저장하고 검증해야할지 도저히 감이 잡히지 않아서 검색을 통해 로직을 찾아봤다.

dp 배열을 map보다 길이가 1 더 크게 설정하고, map 좌상단의 표시를 확인하는 것이었다.

y=1, x=1부터 dp의 끝까지 돌며, map [y-1][x-1]에 표시된 도로 상황을 확인했다.

 

DP[y][x][0] : 아래로 차가 진행하는 루트, DP[y][x][1] : 오른쪽으로 차가 진행하는 루트

 

map [y-1][x-1]

0일 때 : 회전 및 직진이 가능하기 때문에, dp[y][x][0]과 dp[y][x][1] 모두, dp[y-1][x-1][0] (아래로 내려오는 루트)과 dp[y-1][x-1][1] (아래로 내려오는 루트)를 더해주었다. ~> dp[y][x][0 , 1] = dp[y-1][x-1][0] + dp[y-1][x-1][1]

1일 때 : 통행이 불가능한 표시기 때문에,  dp[y][x][0 , 1] = 0 으로 설정해주었다. (루트가 끊김을 표시)

2일 때 : 회전이 불가능한 표시기 때문에,  dp[y][x][0] = dp[y-1][x][0]     ,    dp[y][x][1] = dp[y][x-1][1] 을 저장해주었다. (회전 없는 루트)

 

dp에는 꽤나 자신있다고 생각했는데 아니었다.. 그래서 충격이 크다.. 요즘 슬럼프에 빠진 것 같은데 조급해 하지말고 천천히 다시 올라가야겠다..

 

코드

class Solution {
    int MOD = 20170805;
    public int solution(int m, int n, int[][] cityMap) {
        int answer = 0;
        int[][][] dp = inItDp(cityMap);
        dp = findRoutes(dp, cityMap);
        
        return dp[m][n][0];
    }
    
    private int[][][] inItDp(int[][] cityMap) {
        int[][][] result = new int[cityMap.length+1][cityMap[0].length+1][2];
        result[1][1][0] =1;
        result[1][1][1] =1;
        
        return result;
    }
    
    private int[][][] findRoutes(int[][][] dp, int[][] cityMap) {
        for(int y=1; y<dp.length; y++) {
            for(int x=1; x<dp[y].length; x++) {
                if(cityMap[y-1][x-1] ==0) {
                    dp[y][x][0] += (dp[y-1][x][0] + dp[y][x-1][1]) % MOD;
                    dp[y][x][1] += (dp[y-1][x][0] + dp[y][x-1][1]) % MOD;
                } else if(cityMap[y-1][x-1] ==1) {   // 통행 불가
                    dp[y][x][0] =0;
                    dp[y][x][1] =0;
                } else { // 좌 / 우회전 불가
                    dp[y][x][0] = dp[y-1][x][0];
                    dp[y][x][1] = dp[y][x-1][1];
                }
            }
        }
        return dp;
    }
}