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

- 참고 : programmers.co.kr/learn/courses/30/lessons/1832?language=java

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

 

 

- dp 문제

 

- bfs로 풀려고 했으나 m과 n이 500 이므로 n(500!)의 경우 시간 초과

- dp로 접근하는 것이 현명한 선택이었다.

- 1-indexed 로 접근하는 것이 for구문이 한방에 풀리기 때문에 더 현명한 선택이었다. 

(0-indexed 의 경우 첫 행, 첫 열을 따로 초기화 해주어야 함)

- 0일 경우

   - dp[i][j][0] += dp[i][j-1][0] + dp[i-1][j][1];

   - dp[i][j][1] += dp[i][j-1][0] + dp[i-1][j][1];
     < i, j 번째는 0일 경우 : i-1, j (위쪽에서 온 경우의 수) + i, j-1 (왼쪽에서 온 경우의 수)>

 

- 1일 경우

   - dp[i][j][0] = 0

   - dp[i][j][1] = 0

 

- 2일 경우

   - dp[i][j][0] = dp[i][j-1][0];
     < i, j 번째는 2일 경우 : i-1, j (위쪽에서 온 경우의 수) 를 그대로 진행>

   - dp[i][j][1] = dp[i-1][j][1];

     < i, j 번째는 2일 경우 : i, j-1 (왼쪽에서 온 경우의 수) 를 그대로 진행>

 

 

class Solution {
    int MOD = 20170805;
    
    public int solution(int m, int n, int[][] cityMap) {
        int[][][] dp = new int[m+1][n+1][2];
        dp[1][1][0] = 1; // 왼쪽에서 온 것
        dp[1][1][1] = 1; // 위에서 온 것
        
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(cityMap[i-1][j-1] == 0) {
                    dp[i][j][0] += (dp[i-1][j][1] + dp[i][j-1][0]) % MOD;
                    dp[i][j][1] += (dp[i-1][j][1] + dp[i][j-1][0]) % MOD;
                }
                if(cityMap[i-1][j-1] == 1) {
                    dp[i][j][0] = 0;
                    dp[i][j][1] = 0;
                }
                if(cityMap[i-1][j-1] == 2) {
                    dp[i][j][0] = dp[i][j-1][0];
                    dp[i][j][1] = dp[i-1][j][1];
                }   
            }
        }
        return dp[m][n][0];
    }
}