[동적계획법, 난이도 상] 백준 1890번 점프

동적계획법과 DFS를 동시에 적용해야 하는 높은 난이도의 문제이다.

본인은 이제부터 DFS를 마주쳤다 싶으면 바로 그래프로 도식화해서 풀 것이라고 다짐했다.

이 문제는 두 스텝으로 나누어서 해결했다.

1. 점프할 수 있는 좌표를 모두 경로벡터에 넣는다. 여기에서는 간선이라고 봐도 무방하다.

점프를 했을 때 맵 밖으로 벗어나는 경우도 신경 써줘야한다. 맵 밖으로 떨어진 좌표는 경로벡터에 넣지 않으면 된다.

오른쪽, 아래쪽만 점프 가능하다는 사실을 잊지말자. 

DFS를 도착점부터 역으로 수행할 것이기 때문에 간선 연결 방향은 반대로 했다.

>>  a[i+jump*dx[k]][j+jump*dy[k]].push_back(make_pair(i, j));

 

이 과정이 끝나면 경로는 이렇게 된다.

맨 오른쪽 맨 아래 '0'부터 화살표 방향대로 DFS를 시작한다는 것이다!

 

 

2. DFS를 도착점부터 수행해준다.

DFS를 수행하다가 출발점을 만났다는 의미는, 도착할 수 있는 경우 하나를 만났다는 의미이기 때문에 1을 반환해준다.

확장해서 이해해보면 방문배열d의 좌표값이 1 이상이라는 의미는, 출발점부터 도착점까지 무사히 갈 수 있는 경로에 속해 있다는 의미이기 때문에 그 좌표의 DFS값을 자신의 방문배열d의 좌표값에 더해준다.

이를 반복하면 문제가 해결된다!

 

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
long long d[101][101];
vector<pair<int, int> > a[101][101];
int map[101][101];
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
int n;
long long dfs(int x, int y) {
	if (x == 0 && y == 0) {
		return 1;
	}
	if (d[x][y] == -1) {
		d[x][y] = 0;
		for (int i = 0; i < a[x][y].size(); i++) {
			int x2 = a[x][y][i].first;
			int y2 = a[x][y][i].second;
			d[x][y] += dfs(x2, y2);
		}
	}
	return d[x][y];
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	int coun = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int jump = map[i][j];
			if (jump == 0) continue;
			for (int k = 0; k < 2; k++) {
				if (i + jump*dx[k] < 0 || j + jump*dy[k] < 0 || i + jump*dx[k] >= n || j + jump*dy[k] >= n)	continue;
				if (i + jump * dx[k] == 0 && j + jump * dy[k] == 0) continue;
				a[i+jump*dx[k]][j+jump*dy[k]].push_back(make_pair(i, j));
			}
		}
	}
	memset(d, -1, sizeof(d));
	long long ans;
	ans = dfs(n-1, n-1);
	cout << ans;
}