보행자 천국

BFS를 이용한 문제인줄 알았으나 자세히 보니 자동차는 오른쪽 또는 아래로만 이동이 가능하다 즉 경로를 순회할 일이 없다.
또한 문제에서는 0,0 지점에서 m,n지점까지 갈수있는 방법을 묻는 문제이기때문에 BFS보다는 전체순회를 통한 DP문제에 가까워 보였다.

코드

class Solution {
    int MOD = 20170805;
    int[][][] dp;
    public int solution(int m, int n, int[][] cityMap) {
        int answer = 0;
        dp = new int[m][n][2];
        dp[0][0][1]=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){
                    if(i==0&&j==0){
                        continue;
                    }else if(i==0){
                        dp[i][j][0] += dp[i][j-1][1]%MOD;
                        dp[i][j][1] += dp[i][j-1][1]%MOD;
                    }else if(j==0){
                        dp[i][j][0] += dp[i-1][j][0]%MOD;
                        dp[i][j][1] += dp[i-1][j][0]%MOD;
                    }else{
                        dp[i][j][0] += (dp[i-1][j][0]+dp[i][j-1][1])%MOD;
                        dp[i][j][1] += (dp[i-1][j][0]+dp[i][j-1][1])%MOD;
                    }
                }else if(cityMap[i][j]==1){
                    dp[i][j][0] = 0;
                    dp[i][j][1] = 0;
                }else{
                    if(i!=0)
                        dp[i][j][0] += dp[i-1][j][0];
                    if(j!=0)
                        dp[i][j][1] += dp[i][j-1][1];
                }
            }
        }      
        return dp[m-1][n-1][0];
    }
}

문제를 해결하고 난뒤에 값을 0부터가아닌 패딩값을 추가했다면 if else문이 더 많이 줄어드는걸 확인했다.