[2017 카카오코드예선] 보행자 천국 (LV3)

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

코딩테스트 연습 - 보행자 천국

 

 

[해결방법]

* 위 맵은 오른쪽, 아래 두 방향으로만 이동이 가능하다.

방향이 결과에 영향을 미치기 때문에, 방향정보를 저장할 필요가 있다. 

- 방향에 따른 접근 가능 횟수를  담을 수 있도록 삼차원 배열을 사용한다. DP[y][x][dir] (dir: 0, 1 / 아래, 오른쪽)

현재 위치의 값이 다음 움직임에 영향을 미친다.

 

 

1. 초기 0, 0 의 가짓수는 1로 셋팅해준다. (무조건 시작점은 한 방식으로만 접근이 가능하므로)

2. 시작점에서 오른쪽, 아래로 확인하면서 이동가능하다면 (1이 아니라면) 1로 세팅해준다.

1	1	1
1	0	0
1	0	0

3.  1,1 부터 돌면서 확인을 해준다.

3-1. 현재위치 y, x 의 값이 0 이라면 위, 왼쪽에서 접근이 가능하므로 위, 왼쪽의 값을 합산하여 저장한다.

	3
2	[아래방향] = 3+2 [오른쪽방향] = 3+2

3-2. 현재위치 y, x 가 1 이라면 접근이 불가능하므로 continue 한다.

3-3. 현재위치 y, x, 가 2 라면 위 또는 왼쪽 둘 다 접근이 가능하지만, 동시에 접근은 불가하므로 방향을 분리하여 저장한다.

	3
2	[아래방향] = 3 [오른쪽방향] = 2

 

4. answer = N-1, M-1 [아래방향] +  N-1, M-1 [오른쪽방향] % MOD 

 

[DP 풀이]

#include <vector>
#include <iostream>

using namespace std;

int DP[501][501][2];
int MOD = 20170805;
int N, M;
vector<vector<int>> map;
// 0 down 1 right
int dp(int y, int x, int dir) {
    if(y == 0 && x == 0) return 1;
    if(y < 0 || x <0 || y>= M|| x>= N) return 0;
    
    if(map[y][x] == 0) {
        DP[y][x][0] = (dp(y-1, x, 0) + dp(y, x-1, 1)) % MOD;
        DP[y][x][1] = (dp(y-1, x, 0) + dp(y, x-1, 1)) % MOD;
    }
    else if(map[y][x] == 2) {
        if(dir == 0) {
            DP[y][x][0] = dp(y-1, x, 0) % MOD;
            DP[y][x][1] = 0;
        }
        if(dir == 1) {
            DP[y][x][1] = dp(y, x-1, 1) % MOD;
            DP[y][x][0] = 0;
        }
    }
    else if(map[y][x] == 1) {
        DP[y][x][0] = 0;
        DP[y][x][1] = 0;
    }
    
    return DP[y][x][dir];
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    M= city_map.size();
    N= city_map[0].size();
    map = city_map;
    
    for(int i=0; i<M; i++) {
        for(int j=0; j<N; j++) {
            DP[i][j][0] = 0;
            DP[i][j][1] = 0;
        }
    }
    
    for(int i=0; i<M; i++){
        if(city_map[i][0] == 1)
            break;
        DP[i][0][0] = 1;
    }
    for(int i=0; i<N; i++){
        if(city_map[0][i] == 1)
            break;
        DP[0][i][1] = 1;
    }
    // 0 down 1 right
    for(int i=1; i<M; i++) {
        for(int j=1; j<N; j++) {
            
            if(city_map[i-1][j] == 0) {
                DP[i][j][0] += (DP[i-1][j][0] + DP[i-1][j][1]) %MOD;
            }
            else if(city_map[i-1][j] == 2) {
                DP[i][j][0] += (DP[i-1][j][0] %MOD);    
            }
            if(city_map[i][j-1] == 0) {
                DP[i][j][1] += (DP[i][j-1][0] + DP[i][j-1][1]) %MOD;
            }
            else if(city_map[i][j-1] == 2) {
                DP[i][j][1] += (DP[i][j-1][1] %MOD);    
            }
            else
                continue;
        }
    }
  
    answer = (DP[M-1][N-1][0] + DP[M-1][N-1][1])%MOD;
    
    return answer;
}

 

DFS 시간초과, 테스트 케이스 통과

#include <vector>
#include <iostream>

using namespace std;
const int dy[2] = {1, 0};
const int dx[2] = {0, 1};

int MOD = 20170805;
int M, N;
int answer = 0;
bool visit[501][501];

void dfs(int y, int x, int dir, vector<vector<int>> &arr) {
    if(y == M-1 && x == N-1) {
        answer++;
        return;
    }
   
    for(int i=0; i<2; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];    
        if(ny <0 || nx < 0 || ny>=M || nx >= N || visit[ny][nx] == true) continue;
        if(arr[ny][nx] == 1) continue;
        if(arr[y][x] == 2 && i != dir) continue;
        visit[ny][nx] = true;
        dfs(ny, nx, i, arr);
        visit[ny][nx] = false;
    }  
    
}


// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    answer = 0;
    M = city_map.size();
    N = city_map[0].size();
    
    for(int i=0; i<M; i++)
        for(int j=0; j<N; j++)
            visit[i][j] = false;
    
    visit[0][0] = true;
    dfs(0, 0, 0, city_map);
    visit[0][0] = false;
    
    return answer% 20170805;
}