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

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

대표적인 DP문제이다.
오른쪽과 아래쪽으로만 움직일 수 있기 때문에 다음 DP식이 기본 식이다.

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

추가적으로 city_map[i][j]가 2인 경우엔 왼쪽에서 오는 경우는 오른쪽으로만 움직일 수 있고, 위쪽에서 오는 것은 아래쪽으로만 움직일 수 있다는 조건이 있다.

따라서 (i, j)기준으로 (i-1, j) 혹은 (i, j-1)의 city_map 값이 2라면 (i-k, j) 혹은 (i, j-k)의 dp값을 참고해서 (i, j)값을 업데이트 해줘야 한다(k는 city_map의 값이 2가 아닌 첫 좌표이다).

코드는 아래와 같다.

#include <vector>

using namespace std;

int MOD = 20170805;

int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    m ^= n ^= m ^= n;
    vector<vector<int>> dp(n, vector<int>(m, 0));
    
    dp[0][0] = 1;
    for(int j=1;j<m;j++) 
        dp[0][j] = (dp[0][j - 1] == 0 || city_map[0][j] == 1) ? 0 : 1;
    
    for(int i=1;i<n;i++) 
        dp[i][0] = (dp[i - 1][0] == 0 || city_map[i][0] == 1) ? 0 : 1;
        
    for(int i=1;i<n;i++) {
        for(int j=1;j<m;j++) {
            if(city_map[i][j] == 1) {
                dp[i][j] = 0;
                continue;
            }
            int top = i - 1, left = j - 1;
            if(city_map[top][j] == 2) {
                while(city_map[top][j] == 2 && top >= 0) 
                    top--;
                top = top < 0 ? 0 : dp[top][j];
            } else
                top = dp[top][j];
            
            if(city_map[i][left] == 2) {
                while(city_map[i][left] == 2 && left >= 0) 
                    left--;
                left = left < 0 ? 0 : dp[i][left];
            } else
                left = dp[i][left];
            
            dp[i][j] = (top + left) % MOD;
        }
    }
    
    answer = dp[n - 1][m - 1];
    
    return answer;
}