[pro] 프로그래머스 level3 1832 보행자 천국 (Java) - dp

[문제]

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

프로그래머스

 

[풀이]

처음 i-1, j-1에 대해서 배열 범위 오류가 나지 않도록 dp 배열에 패딩을 넣어준다. 이에 따라 cityMap의 (0,0)이 dp 배열의 (1,1)과 매핑된다는 것을 헷갈리지 않도록 주의해야 한다.

 

cityMap이 2인 경우, 왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다. 이 조건을 판단하기 위해서는 왼쪽에서 오던 차인지, 위에서 오던 차인지 방향에 대한 기록이 필요하므로 dp 배열을 3차원으로 선언한다.

 

1) cityMap이 0인 경우. 위에서 오는 경우와 아래에서 오는 경우를 모두 저장

dp[r][c][0] += (dp[r-1][c][0]+dp[r][c-1][1])%MOD;
dp[r][c][1] += (dp[r-1][c][0]+dp[r][c-1][1])%MOD;

2) cityMap이 1인 경우, 통행이 금지되어 지나갈 수 없음. 즉 가능한 경로가 0.

dp[r][c][0] = 0;
dp[r][c][1] = 0;

3) cityMap이 2인 경우, 원래의 이동 방향으로만 이동 가능함

dp[r][c][0] += dp[r-1][c][0]%MOD; -> 위에서 아래로 오는 방향의 경로만 저장
dp[r][c][1] += dp[r][c-1][1]%MOD; -> 왼쪽에서 오른쪽으로 가는 방향의 경로만 저장

 

cityMap[m-1][n-1]은 무조건 0이기 때문에 dp[m][n][0]과 dp[m][n][1]에는 모두 (위에서 오는 경로+왼쪽에서 오는 경로)가 똑같이 저장되어 있다. 따라서 하나만 정답으로 반환해주면 된다.

 

[코드]

 

class Solution {
    int MOD = 20170805;
    int[][][] dp;
    public int solution(int m, int n, int[][] cityMap) {
        int answer = 0;
        //왼쪽 위의 출발점에서 오른쪽 아래 도착점까지 자동차로 이동 가능한 전체 가능한 경로 수를 출력하는 프로그램을 작성하라
        dp = new int[m+1][n+1][2]; //0-아래로 1-오른쪽으로 이동
        
        dp[1][1][0] = dp[1][1][1] = 1;
        for(int r=1; r<=m; r++){
            for(int c=1; c<=n; c++){
                if(cityMap[r-1][c-1]==0){
                    dp[r][c][0] += (dp[r-1][c][0]+dp[r][c-1][1])%MOD;
                    dp[r][c][1] += (dp[r-1][c][0]+dp[r][c-1][1])%MOD;
                }
                else if(cityMap[r-1][c-1]==1){
                    //통행이 금지된 지점
                    dp[r][c][0] = 0;
                    dp[r][c][1] = 0;
                }
                else{
                    dp[r][c][0] += dp[r-1][c][0]%MOD;
                    dp[r][c][1] += dp[r][c-1][1]%MOD;
                }
            }
        }
        return dp[m][n][0];
    }
}