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

나는 이 문제를 dfs로 접근했다.
각 칸을 경로로 생각하고
1. 0을 만나면 2방향을 모두 탐색
2. 1을 만나면 탐색 중지
3. 2를 만나면 이전 방향이 오른쪽 진행이면 오른쪽으로 이동 아래로 진행이면 아래로 이동 
하도록 코드를 짰다.

하지만 코드를 실행하면 실패가 떴다..
코드는 아래와 같다.

#include <vector>
#include <iostream>

using namespace std;

int MOD = 20170805;
bool visit[501][501];
void dijkstra(int x, int y, int m, int n, const vector<vector<int>>& city_map, int dir, int* dx, int* dy, int& answer)
{ 
    if(y == m - 1 && x == n - 1)
    {
        ++answer;
        return;  
    }
    
    for(int i = 0; i < 2; ++i)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx < 0 || nx >= n || ny < 0 || ny >= m)
            continue;
        
        if(city_map[ny][nx] == 1)
            continue;
        
        if(city_map[y][x] == 2)
        {
            if(dir == 0 && (i != dir))
                continue;
            
            if(dir == 1 && (i != dir))
            {
                continue;
            }
        }
        
        if(visit[ny][nx] == false)
        {
            visit[ny][nx] = true;
            dijkstra(nx, ny, m, n, city_map, i, dx, dy, answer);
            visit[ny][nx] = false;
        }
    }
    return;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) 
{
    int dx[2] = {1, 0};
    int dy[2] = {0, 1};
    int answer = 0;
   // vector<vector<bool>> visit = vector<vector<bool>>(m,vector<bool>(n, false));
    
    visit[0][0] = true;
    dijkstra(0, 0, m, n, city_map, 0, dx, dy, answer);
    return answer % MOD;
}

따라서 난 다른 사람 풀이를 봤다.
정확하게 내 코드가 어디가 잘못되는지 확인을 해야했지만
다시 문제를 봐도 모르겠더라....

인터넷 풀이는 DP를 사용하여 풀었다.

통행 금지를 만나기 전까지 1열, 1행에 해당하는 dp를 1로 초기화했다.
(한 방향으로만 진행하는 것은 경우의 수가 1임을 알 수 있으므로)

1. 왼쪽에서 오른쪽으로 이동한 경우
1-1) 현재가 0이면 (위에서 아래로 온 경우의 수 + 왼쪽에서 오른쪽으로 온 경우)의 수를 합했다.
1-2) 현재가 2이면 (왼쪽에서 오른쪽으로 온 경우)의 수만 합했다.

2. 위에서 아래쪽으로 이동한 경우
2-1) 현재가 0이면 (위에서 아래로 온 경우의 수 + 왼쪽에서 오른쪽으로 온 경우)의 수를 합했다.
2-2) 현재가 2이면 (위에서 아래쪽으로 온 경우)의 수만 합했다.

3. 현재가 0이면 탐색을 진행하지 않았다.

#include <vector>
#include <iostream>

using namespace std;

int MOD = 20170805;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) 
{
    int answer = 0;
    
    vector<vector<vector<long long>>> DP = vector<vector<vector<long long>>>
        (m + 1, vector<vector<long long>>(n + 1, vector<long long>(2)));
    
    //세로 한쪽 방향으로만 진행 할 수 있는 경우의 수는 1
    for(int i = 0; i < m; ++i)
    {
        if(city_map[i][0] == 1)
            break;
        DP[i][0][1] = 1;
    }
    
    //가로 한쪽 방향으로만 진행 할 수 있는 경우의 수는 1
    for(int i = 0; i < n; ++i)
    {
        if(city_map[0][i] == 1)
            break;
        DP[0][i][0] = 1;
    }
    
    for(int i = 1; i < m; ++i)
    {
        for(int j = 1; j < n; ++j)
        {
            if(city_map[i][j] == 1)
                continue;
         
         	//왼쪽에서 왔는데, 자유롭게 온 경우는 왼쪽과 위에서 온 경우가 될 수 있다
            if(city_map[i][j - 1] == 0)
            {
                DP[i][j][0] += (DP[i][j - 1][0] + DP[i][j - 1][1]) % MOD; 
            }
            //왼쪽에서 왔는데, 우회전이 위에서 오는 것이 금지되고, 우회전만 가능하다.
            else if(city_map[i][j - 1] == 2)
            {
                DP[i][j][0] += DP[i][j - 1][0] % MOD;    
            }
            //위에서 왔는데, 자유롭게 온 경우는 왼쪽과 위에서 온 경우가 될 수 있다.                
            if(city_map[i - 1][j] == 0)
            {
                DP[i][j][1] += (DP[i - 1][j][0] + DP[i - 1][j][1]) % MOD; 
            }
            //위에서 왔는데, 우회전이 금지되고, 위에서 온 경우만 될 수 있다
            else if(city_map[i - 1][j] == 2)
            {
                DP[i][j][1] += DP[i - 1][j][1] % MOD;    
            }
        }   
    }
     
    answer = (DP[m - 1][n - 1][0] + DP[m - 1][n - 1][1]) % MOD;
    return answer;
}