[프로그래머스 lv3] 보행자 천국 풀이

해설

(x, y)에 d 방향으로 들어왔을 때 (m-1, n-1)까지 도달하는 경우의 수를 dfs(d, x, y)로 설정한다.

리턴값은 다음과 같다.

 

1)  x == m-1 && y == n-1 일 때: 자기 자신에서 자기 자신으로 가는 경우의 수는 1이므로 1을 리턴한다.

 

2) (x, y)에서 이동할 수 있는 방향 k는 오른쪽(0)과 아래쪽(1)이다. 이때, 해당 방향으로 이동이 가능하려면,

- 이동한 좌표가 city_map 내부 범위에 있어야 하고

- city_map[x][y]가 0으로 자유롭게 이동이 가능하거나, city_map[x][y]가 2이면서 d와 이동 방향 k가 같아야 한다.

- 즉, city_map[x][y] == 0 || (city_map[x][y] == 2 && d == k) 이면 해당 방향으로 이동 가능하다.

 

이동할 수 있는 방향의 좌표로 부터 (m-1, n-1)까지 도달하는 경우의 수 dfs(int k, int nx, int ny)를 모두 더한다. 이후, MOD로 나누어 dfs(d, x, y) 값을 완성한다.

 

3) 이미 구한 값을 활용하기 위해 memo[d][x][y]에 결과를 기록한다. dfs(d, x, y) 호출 시 이미 구한 값이 있다면 별도의 계산 없이 memo[d][x][y]를 리턴한다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int MOD = 20170805;
int memo[2][505][505];

int dx[2] = {0, 1};
int dy[2] = {1, 0};

bool OOB(int x, int y, int m, int n) {
    return 0 > x || x >= m || 0 > y || y >= n;
}

int dfs(int d, int x, int y, int m, int n, const vector<vector<int>>& city_map) {
    
    if (x == m-1 && y == n-1) return 1;
    if (memo[d][x][y] != -1) return memo[d][x][y];
    
    int ret = 0;
    for (int k=0; k<2; k++) {
        int nx = x+dx[k];
        int ny = y+dy[k];
        if (OOB(nx, ny, m, n)) continue; 
        if (!city_map[x][y] || (city_map[x][y] == 2 && d == k)) {
            ret += dfs(k, nx, ny, m, n, city_map);
            ret %= MOD;
        }
    }
    
    return memo[d][x][y] = ret;
}

int solution(int m, int n, vector<vector<int>> city_map) {

    memset(memo, -1, sizeof(memo));
    return dfs(0, 0, 0, m, n, city_map);    
}