Programmers > 카카오코드 예선 > 보행자 천국

이 문제를 풀기위해서 우리가 학창시절 수학시간에 배웠던 길찾기 방법을 사용하였다.

이런식으로 목적지까지 경로의 가짓수를 구하는 것이었는데 아마 그림을 보면

옛날에 이런걸 했던 기억이 어렴풋이나마 날 것이라고 생각한다.

그런데 이 문제에서 문제점은 지나갈 수 없는 곳도 있고 좌회전 or 우회전을 못하는 지점이

있다는 것이다.

그런 문제점을 해결하기 위해 우측으로 갈 수 있는 경로의 수와

아래로 갈 수 있는 경로의 수를 따로 계산하였다.

 

위 그림에서 보면 1번 케이스인 경우 우측, 아래로 모두갈 수 없으므로 두 배열값이 0이 된다.

2번 케이스의 경우 우회전,좌회전을 할 수 없으므로 아래로 갈 수 있는 경우의 수는

위의 좌표에 있는 경우의 수를 그대로 가져오고 우측으로 가는 경우의 수도 마찬가지로

왼쪽에 있는 경우의 수를 그대로 가져온다.

0번같이 자유롭게 갈 수 있는 경우 두가지 경우의 수를 더하는게 배열값이 된다.

이런식으로 동적 계획법 방식으로 코드를 구현하였고 

i 나 j 가 0인경우는 조금 다르게 처리해야되기 떄문에 이 부분만 따로 처리 후 위의 방식으로

구현하였다.

#include <vector>
#include <iostream>

using namespace std;

int MOD = 20170805;

int to_next[500][500];
int to_bottom[500][500];
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    to_next[0][0] = 0; to_bottom[0][0] = 0;
    bool x = true;

    for(int i=1; i<n; i++){
        if(city_map[0][i] == 1) x = false;
        if(!x) {to_next[0][i] = 0;
                to_bottom[0][i] = 0;
               }
        else if(city_map[0][i] == 2){
            to_next[0][i] = 1;
            to_bottom[0][i] = 0;
        }
        else{
            to_next[0][i] = 1; to_bottom[0][i] = 1;
        }
    }

    x = true;
    for(int i=1; i<m; i++){
        if(city_map[i][0] == 1) x = false;
        if(!x){
            to_next[i][0] = 0; to_bottom[i][0] = 0;
        }
        else if(city_map[i][0] == 2){
            to_next[i][0] = 0; to_bottom[i][0] = 1;
        }
        else{
            to_next[i][0] = 1; to_bottom[i][0] = 1;
        }
    }

    for(int i=1; i<m; i++){
        for(int j=1; j<n; j++){
            if(city_map[i][j] == 1){
             to_next[i][j] = 0; 
             to_bottom[i][j] = 0;
            }
            else if(city_map[i][j] == 2){
                to_next[i][j] = to_next[i][j-1] % MOD;
                to_bottom[i][j] = to_bottom[i-1][j] % MOD;
            }
            else{
                to_next[i][j] = (to_next[i][j-1] + to_bottom[i-1][j]) %MOD;
                to_bottom[i][j] = (to_next[i][j-1] + to_bottom[i-1][j]) %MOD;
            }
        }
    }

    return to_next[m-1][n-1];
}