[프로그래머스/Level 3] 보행자 천국 (C++)

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

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

DFS와 DP를 이용하여 해결한 문제입니다. 문제의 조건 중, '2번' 사항을 구현하는 것이 약간 어려움을 겪었고, 결국 다른 풀이를 보며 힌트를 받아 코드를 작성했습니다. dp 저장 배열을 3차원으로 선언하고, 현재 좌표를 기준으로 값이 2일 때, for문으로 진행하는 방향(i)과 DFS를 진행하면서 저장된 이전 방향(z)이 같은 경우에만 다음 탐색을 진행하게끔 구현하는 것이 포인트였습니다.

 

#include <vector>
#include <cstring>
using namespace std;

int MOD = 20170805, r, c;
int dp[501][501][2]; // x, y좌표와 방향
int dx[2] = {1, 0};
int dy[2] = {0, 1};

int DFS(int x, int y, int z, vector<vector<int>>& city_map) {
    if(x == r - 1 && y == c - 1) return 1;
    if(dp[x][y][z] != -1) return dp[x][y][z] % MOD;
    dp[x][y][z] = 0;
    
    for(int i = 0; i < 2; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && nx < r && ny >= 0 && ny < c && city_map[nx][ny] != 1) {
            if(city_map[x][y] == 0 || (city_map[x][y] == 2 && i == z)) {
                dp[x][y][z] += DFS(nx, ny, i, city_map);
            }
        }
    }
   
    return dp[x][y][z] % MOD;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    r = m
    c = n;
    memset(dp, -1, sizeof(dp));
    
    return DFS(0, 0, 0, city_map);
}

 

#include <vector>
using namespace std;

int MOD = 20170805;
int dp[501][501][2];

int solution(int m, int n, vector<vector<int>> city_map) {
    dp[0][1][0] = dp[0][1][1] = 1;
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            // case 1-1 : (i,j)에서 아래쪽으로 진행하려고 할 때, 경우의 수는 (i-1,j)에서 아래쪽으로 들어오는 경우 + (x,y-1)에서 오른쪽으로 들어오는 경우
            // case 1-2 : (i,j)에서 오른쪽으로 진행하려고 할 때, 경우의 수는 (i-1,j)에서 아래쪽으로 들어오는 경우 + (i,j-1)에서 오른쪽으로 들어오는 경우
            if(city_map[i - 1][j - 1] == 0) {
                dp[i][j][0] = (dp[i - 1][j][0] + dp[i][j - 1][1]) % MOD;
                dp[i][j][1] = (dp[i - 1][j][0] + dp[i][j - 1][1]) % MOD;
                
            // case 2 : (i,j)에서 아래쪽, 오른쪽으로 진행하려고 할 때, 통행 금지이므로 경우의 수는 0
            } else if(city_map[i - 1][j - 1] == 1) {
                 dp[i][j][0] = dp[i][j][1] = 0;
                 
            // case 3-1 : (i,j)에서 아래쪽으로 진행하려고 할 때, 원래 방향으로만 가야 하므로 경우의 수는 (i-1,j)에서 아래쪽으로 들어오는 경우
            // case 3-2 : (i,j)에서 오른쪽으로 진행하려고 할 때, 원래 방향으로만 가야 하므로 경우의 수는 (i,j-1)에서 오른쪽으로 들어오는 경우
            } else if(city_map[i - 1][j - 1] == 2) {
                dp[i][j][0] = dp[i - 1][j][0] % MOD;
                dp[i][j][1] = dp[i][j - 1][1] % MOD;
            }
        }
    }
    
    return dp[m][n][0];
}