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

문제

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

프로그래머스

 

---

단순 bfs/dfs로는 시간초과가 발생하는 dp 문제

오른쪽 혹은 아래로만 이동할 수 있기 때문에 dp 배열을 dp[m+1][n+1][2]로 생성

• dp[i][j][0]: (i, j) 위치에 도달할 수 있는 경로 중 위에서 내려온 경로의 수
• dp[i][j][1]: (i, j) 위치에 도달할 수 있는 경로 중 왼쪽에서 온 경로의 수

cityMap이 0일 때(자동차가 자유롭게 이동할 수 있는 경우) dp[i][j][0], dp[i][j][1]을 더해서 갱신하기 때문에 

return은 dp[i][j][0]만 해줘도 정답

 

import java.util.*;
class Solution {
    static int MOD = 20170805;
    public int solution(int m, int n, int[][] cityMap) {
        int answer = 0;
        
        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][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-1][j-1] == 1) {
                    dp[i][j][0] = 0;
                    dp[i][j][1] = 0;
                } else {
                    dp[i][j][0] = dp[i-1][j][0];
                    dp[i][j][1] = dp[i][j-1][1];
                }
            }
        }        
        return dp[m][n][0];
    }
}