[백준] 1890. 점프

문제

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.

 

실버 1 DFS+DP 문제입니다

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll visited[101][101];
ll mp[101][101];

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

ll dfs(ll y, ll x) {
	if (y == n - 1 && x == n - 1)return visited[y][x] = 1;

	if (visited[y][x] != -1)return visited[y][x];

	visited[y][x] = 0;
	for (ll i = 0; i < 2; i++) {
		ll ny = y + dy[i]*mp[y][x];
		ll nx = x + dx[i]*mp[y][x];

		if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
			visited[y][x] += dfs(ny, nx);
		}
	}
	return visited[y][x];
}
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	memset(visited, -1, sizeof(visited));
	memset(mp, 0, sizeof(mp));
	ll x;
	cin >> n;
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < n; j++) {
			cin >> x;
			mp[i][j] = x;
		}
	}
	cout << dfs(0, 0);
}

visited배열을 -1로 초기화하고, 메모라이제이션을 이용해서 모든 깊이를 탐색하지 않습니다.