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

문제 설명

네비게이션을 개발하고자 합니다. 도로는 2차원 배열(최대 크기 500*500, 값 0 : 제한없음 1: 못감 2: 직진만 가능)로 주어지고, 자동차는 오른쪽 또는 아래방향으로 한칸씩 이동할 수 있습니다.
이 때 (0,0)위치에서 (M-1,N-1)위치로 이동할 수 있는 길의 가짓수를 MOD로 나눈 나머지로 구하세요

아이디어

DP임을 MOD때문에 알앗다.. DP로 각 자리에 갈 수 있는 방법의 수를 관리하고, 숫자를 채울 때는 연결되어 있는 부분의 가짓수를 갖다 쓰면 되겠다는 생각을 했다. 그리고 갖다 쓸 때도 직진만 가능한 경우 때문에 각 방향으로 인풋이 들어왔을 때의 가짓수를 따로 저장해야겠다는 생각을 했다. 점화식은 코드에 있다.
그리고 2차원 배열을 돌면서 현재 보고 있는 자리가 영향을 미칠 수 있는 곳에 영향을 미치는 식으로 구현했다.(이렇게 했을 때 한 칸의 type에 대해서 고려를 할 수 있어 좋았다.)

삽질

근데 자동차가 오른쪽, 아래로만 움직일 수 있다는 걸 못 읽어서 왼쪽,위로 간다면? 이거 때문에 고민이 많았다. 왜냐하면 이렇게 되면 내가 옆칸에 영향을 미치기도 하고 옆칸이 나한테도 영향을 미치기 때문이다...
근데 갈 수 있는 방향이 오른쪽 아래로 한정이되자 왼위에서 오른쪽아래로 가는 대각선으로 영향을 미친다고 생각해도 괜찮았다.

코드

#include <vector>
#include<iostream>
#include<string>
using namespace std;

int MOD = 20170805;
int di[] = {0,-1};
int dj[] = {-1,0};
int tab[501][501][2];//2개 버전(왼쪽에서 오는 거 위에서 오는 거)
int m, n;//m이 세로 n이 가로
vector<vector<int>> city_map;
int verify_2017(int n){
    return n%MOD;
}
void i_affect(int i, int j){//더한 후에 2017....verify 필요
    int cur = city_map[i][j];
    if(cur == 0){//양쪽에 다 영향
        int sum_cur = tab[i][j][0]+tab[i][j][1];
        tab[i+1][j][1] += sum_cur; tab[i+1][j][1] = verify_2017(tab[i+1][j][1]);
        tab[i][j+1][0]+=sum_cur; tab[i][j+1][0] = verify_2017(tab[i][j+1][0]);
    }
    else if(cur ==2){//한쪽만 영향
        tab[i+1][j][1] += tab[i][j][1];tab[i+1][j][1] = verify_2017(tab[i+1][j][1]);
        tab[i][j+1][0] +=tab[i][j][0];tab[i][j+1][0] = verify_2017(tab[i][j+1][0]);
    }
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int mm, int nn, vector<vector<int>> cm) {
    int answer = 0;
    city_map = cm;
    m = mm;
    n= nn;
    for(int i = 0;i<=m;i++){
        for(int j = 0;j<=n;j++){
            tab[i][j][0] = 0;
            tab[i][j][1] = 0;
        }
    }
    tab[0][1][0] =1;
    tab[1][0][1] = 1;
    for(int i = 0;i<m;i++){
        for(int j = 0;j<n;j++){
            i_affect(i,j);
        }
    }
    answer= verify_2017(tab[m-1][n-1][0]+tab[m-1][n-1][1]);
    return answer;
}