[프로그래머스] level 3 - 보행자 천국, C++

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

프로그래머스

본 문제는 2017 카카오코드 예선 문제로 DFS 문제를 활용한 DP 문제다. 예를들어 DP 문제는 d[i] = MAX( d[i-1], d[i-2] )와 같이 작은 문제로 나누어 계산하는 방식인데 중복되는 경우가 많을 경우 1번만 계산을 하여 연산량을 줄이는 방법이다.

/* 개인적인 DP 문제 해결 방법은 점화식이 바로 떠오르면 아! DP 문제구나 하고 bottom up으로 풀다. 그게 아니면 먼저 모든 경우를 다 탐색해보고 제출한다. 그러면 몇몇 테스트 케이스에서 시간초과를 받는다. 그러면 아.. DP구나 하고 재귀로 다시 코드를 작성하고 배열을 return한다. 아직 PS 초보라 이렇게 밖에 못하겠다.. */

DFS는 재귀를 이용한 방식으로 여기서 메모이제이션을 하면 top down의 DP 문제를 해결할 수 있다. 이때 배열은 3차원 배열을 사용하였는데 위에서 내려오는 경우와 왼쪽에서 내려오는 경우를 구분하기 위해 사용하였다.

#include <vector>
#include <cstring>
 
using namespace std;
 
int MOD = 20170805;
int d[501][501][2];
int dx[] = {1, 0};
int dy[] = {0, 1};
int N;
int M;
 
int cal (int x, int y, int z, vector<vector<int>> &MAP) {
    if (x == N-1 && y == M-1) return 1;
    if (d[x][y][z] != -1) return d[x][y][z];
    d[x][y][z] = 0;
    for (int k = 0; k < 2; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
            if (MAP[x][y] == 0 || (MAP[x][y] == 2 && k == z)) {
                d[x][y][z] += cal(nx, ny, k, MAP) % MOD;
            }
        }
    }
    return d[x][y][z] % MOD;
}
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    memset(d, -1, sizeof(d));
    
    N = m;
    M = n;
    int answer = cal(0, 0, 0, city_map);
    return answer;
}