백준 5014 스타트링크 - C++ DP

아주아주 간단한 문제다. 보기에는.

하지만 DFS로 풀기에는 좀 까다롭다.

왜냐하면 Floor 가 100만 층이나 되기 때문에

최악의 경우(S 1 G 1,000,000 U 1 같은) 100만번을 쌩으로 돌릴 수도 있기 때문이다. 

depth 가 너무 깊어지기 때문에 터지기 쉽상이므로 다른 방식을 생각해본다.

 

가장 먼저 생각한 것은 동적 계획법(Dynamic programming)이다. 

프로그램을 돌리면서 과거보다 결과가 좋지 않은 것은 전부 쳐내버리는 방법인데, 

가령 길을 찾을 때, 옛날에 지나갔던 길이라면 내가 어떻게 애를 써도 그 시간보다 과거로 가서 길을 지나갈 순 없다.

특히 그곳이 목적지였다면 나는 과거에 도착한 것을 알기 때문에 목적지를 구태여 빙 돌아서 한 번 더 갈 필요는 없다.

 

DP가 딱 그런 뜻이다.

과거를 기록하여 현재와 비교하면서 쳐내거나 더 들어가는 것.

int used[MAXN];
queue<int> q;
int sol() {
	q.push(S);
	used[S] = 0;
	int find = 0;
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		//printf("%d\n", cur);
		if (cur == G) { find = 1; continue;}
		int nextup = cur+U;
		int nextdown = cur - D;
		if (nextup > 0 && nextup <= F) {
			if (used[nextup] > used[cur] + 1) {
				used[nextup] = used[cur] + 1;
				q.push(nextup);
			}
		}
		if (nextdown > 0 && nextdown <= F) {
			if (used[nextdown] > used[cur] + 1) {
				used[nextdown] = used[cur] + 1;
				q.push(nextdown);
			}
		}
	}
	if (!find) return -1;
	return used[G];
}

 

S 점에서 출발하여 G까지 도달하는데 어떤 것이 가장 빠르게 도착할 수 있을까.

S 부터 G로 가는 모든 길에서 언제 어디에 있었는지 기록한다면 쉽게 알 수 있을 것이다.

모두 수행하고 난 후 최종적으로 G에 도착한 시간 중 가장 빠른 시간만을 알면 되기 때문이다.

 

그를 위해 used 라는 DP배열을 선언하고 언제 어디에 들렀는지를 기록한다.

queue 에는 지금 나의  시간과 장소를 기록하고 다음 시간이 왔을 때 이동하도록 한다.

 

만약 지금 나의 위치가 목적지(if (cur == G)였다면 굳이 다른 곳을 갈 필요 없으므로

적어도 한 번 목적지에 들렀다는 표시인 find를 1로 on 시켜주고 다시 q에서 하나를 빼서 수행한다.

 

내가 갈 수 있는 곳은 두 곳인데, U버튼을 눌렀을 때의 하나와 D버튼을 눌렀을 때의 하나다.

U의 경우, 만약 올라갔는데 과거의 내가 들렀던 층이라면 굳이 다시 들를 필요가 없다.

아무리 애써봐야 과거보다 먼저 도착할 순 없기 때문이다.

이럴 경우 이 층을 q에 넣어주지 않는다.

만약 안들렀다면 현재 시간에 +1 (used[nextup] = used[cur] + 1 ) 을 한 것을 기록하고 그 위치를 q에 저장하자.

D의 경우도 마찬가지이다.

 

정해진 건물 층수(1~F)를 벗어나지 않도록 범위에 제한을 두면서 q가 빌때까지 수행한다.

만약 한 번이라도 들렀다면(find==1) used[G]를 return 하여 목적지에 들른 가장 빠른 시간대를 돌려주고

방문하지 않았다면 -1을 return 하여 "use the stairs" 메세지를 출력할 수 있게 해준다.

 

dp 배열은 상당히 빠른 속도를 자랑하는데, 실제로 백만 층을 해봐야 많이 쳐줘도 2백만번의 계산을 수행한다.

하지만! 더 최적화를 하고 싶다면, 올라가거나 내려가기만 하는 연산을 생략하고(층을 U나 D로 나눠준 몫을 더해주면된다) G와 최대한 가까워진 상태에서 범위에 제한을 둬 dp를 수행하면 훨씬 빠를 것 같다.

 

전체코드

#include <iostream>
#include <queue>
using namespace std;
#define MAXN 1000001

int F, S, G, U, D;


//완전탐색
int used[MAXN];
queue<int> q;
int sol() {
	q.push(S);
	used[S] = 0;
	int find = 0;
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		//printf("%d\n", cur);
		if (cur == G) {find = 1;continue;}
		int nextup = cur+U;
		int nextdown = cur - D;
		if (nextup > 0 && nextup <= F) {
			if (used[nextup] > used[cur] + 1) {
				used[nextup] = used[cur] + 1;
				q.push(nextup);
			}
		}
		if (nextdown > 0 && nextdown <= F) {
			if (used[nextdown] > used[cur] + 1) {
				used[nextdown] = used[cur] + 1;
				q.push(nextdown);
			}
		}
	}
	if (!find) return -1;
	return used[G];
}


int main() {
	cin >> F >> S >> G >> U >> D;
	//for (int i = 0; i <= F; i++) {
	//	used[i] = 987654321;
	//}
	int ans = sol();
	if (ans == -1) printf("use the stairs\n");
	else
		printf("%d\n", ans);
}