다이나믹 프로그래밍으로 최적화 하는 DFS, 백준 2253번 점프

 

백준 2253번 점프 문제는

 

N이 최대 10000까지 가능한 문제였습니다.

 

그냥 DFS를 활용해 모든 경우의 수로 점프를 하기에는,  돌담마다 JUMP += -1,0,1 의 세가지 경우가 주어지므로

 

모든 경우의 수를 찾기에는 지수승의 형태 뜁니다.

 

일반적인 BFS로 풀기에는 현재 도착한 돌담이, 최단의 점프로 도착했다는 보장은 되지만,

앞으로도 현재 돌담에서 가지고 있는 JUMP의 크기를 가지고 출발한것이 최단으로 목적지같이 도착한다는 보장이 없습니다.

 

그렇다면 BFS로 visit을 잡을 변수로는 JUMP크기와 돌담 위치를 함께 잡아 주어야합니다.

즉 JUMP크기를 1로 돌담3에 온 경우와 JUMP크기 3으로 돌담3에 온 경우는 구분해 주어야 합니다.

 

이번 문제는 약간의 변형으로 쉽게 BFS로 풀 수 있습니다.

하지만 지금처럼 단계가 최소일때가 최단인 문제가 아니라면,

BFS로 푸는 것은 매우 복잡해 질 수 도 있습니다.

 

그렇다면, 최적의 문제를 풀떄 특화된 dynamic programing을 DFS의 형태로 푸는 방법이 있습니다.

 

stack의 성질을 가진 DFS를 통해 dynamic programing을 응용할 수 있습니다.

 

DFS는 스택의 특성을 가지고 있으므로, 지금까지 어떤 경로로 왔는지는 알 수 없지만,

리턴됬을 때 자신의 상태를 기억할 수 있습니다. 

 

이 상태일때 정답까지 갔다온 최적의 값을 기억 해 놓는다면, 다음번 DFS가 다른 경우의 수로

이 상태를 다시 찾아 왔을때 굳이 한번 더 갈 필요 없이 기억 해놓은 숫자만 바로 리턴하여 사용하면됩니다.

 

이런 저장 기법을 메모이제이션(memoization)이라고 합니다.

다이나믹 프로그래밍은 이런 메모이제이션을 통해 최적문제를 푸는 기법으로,

 

최적의 문제를 풀때, 그 문제를 또다른 최적의 여러 문제들로 해결할 수 있다면 사용 할 수 있는 기법으로

 

미리 작게 쪼갠 최적의 문제들을 푼뒤 값을 저장해두어, 필요에 따라 불러들이며 빠르게 푸는 기법입니다.

 

!!

 

DFS를 통해 재귀적으로 작은 문제들로 쪼개고, 기저를 통해 풀게 된 문제들은 저장해놓습니다.

 

단, 이 문제의 경우 저장해야될 상태가, 점프크기와 현재 돌의 위치 2가지 임을 주의 하셔야합니다. 

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<map>
using namespace std;

int N, M;
map<int,vector<int>> dpMap;
map<int, bool> check; //작은돌 위치

int dp(int pos,int jump) {
	//기저
	if (pos >= N) return -1;
	if (pos == N - 1) return 1;
	if (check.count(pos)) return -1;
	//처음 오는 점프 크기라면, vector를 N만큼 할당.
	if (!dpMap.count(jump)) {
		dpMap[jump] = vector<int>(N, 0);
	}
	if (dpMap[jump][pos]) return dpMap[jump][pos];
	if (!jump) return -1;

	int list[3] = { jump + 1,jump,jump - 1 };
	int mmin = 987654321;
	int temp = 0;
	//3가지 형태로 점프.
	for (int i = 0; i < 3; i++) {
		temp = dp(pos + list[i], list[i]);
		if (temp != -1) {
			mmin = min(mmin, temp);
		}
	}

	//점프와 위치를 상태로서 메모이제이션!!
	if (mmin == 987654321) return dpMap[jump][pos] = -1;
	else 
		return dpMap[jump][pos] = mmin + 1;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N >> M;

	int temp;
	for (int i = 0; i < M; i++) {
		cin >> temp;
		check[temp - 1] = true;
	}

	cout << dp(1, 1);
}