해설
(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);
}
'ㄴ 알고리즘 > 프로그래머스풀이' 카테고리의 다른 글
[프로그래머스 lv3] 외벽 점검 풀이 (0) | 2022.09.17 |
---|---|
[프로그래머스 lv3] 110 옮기기 풀이 (0) | 2022.09.15 |
[프로그래머스 lv3] 길 찾기 게임 풀이 (0) | 2022.09.14 |
[프로그래머스 lv3] 양과 늑대 풀이 (0) | 2022.09.13 |
[프로그래머스 lv3] 기둥과 보 설치 풀이 (0) | 2022.09.13 |
댓글