경로추적

이때까지의 dp/BFS는 최댓값, 최솟값만 구했다.
이제부터는 실제 해를 경로로 찾아보자.

기본적으로 dp/BFS를 푸는방법과 동일하며 path를 이용하여 재귀적으로 찾는다.

예제. 1로만들기 2
주어진 수를 3가지 연산을 통해 1로 만드는 최소 횟수와 그 경로를 묻고있다.

queue<int> q;
.....
cur = q.front();
....
if(...){
	dp[next] = dp[cur] + 1;
	path[next] = cur;
	q.push(next);
}

그럼 최단거리는 어떻게 찾을까?
path[x]는 'x 직전의 수' 라고 정의하고, 이를 재귀적으로 추적한다.
예시2의 10인 경우,
path[5] = 10, path[9] = 10
path[4] = 5, path[3] = 9
path[8] = 9, path[2] = 4
path[1] = 3, path[7] = 8

1로 만들기이므로 path[1]에서부터 역추적하면
1->3->9->10이다.
경로를 순차적으로 출력해야하므로, 스택에 경로를 저장했다.

int x = 1;
stack<int> st;
while (x != n) {
	st.push(x);
	x = path[x];
}
st.push(x);
while (!st.empty()) {
	printf("%d ", st.top());
	st.pop();
}

유제1. 가장 긴 증가하는 부분 수열 4

유제2. DSLR
경로를 항상 역방향으로 추적하지 않는다.
이 문제는 BFS를 하기 위한 queue에 경로도 함께 push하여 계산한다.

queue<pair<int, string>> q;
q.push(make_pair(n, ""));
.....
if(...){
    q.push(make_pair(S, str + "S"));
    ....
}

[예제1 소스코드]

#include <stdio.h>
#include <queue>
#include <stack>
using namespace std;
#define N 1000001
int n;
int dp[N];
int path[N];

int main() {
	scanf("%d", &n);
	dp[n] = 0;
	queue<int> q;
	q.push(n);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		int next3 = cur / 3;
		int next2 = cur / 2;
		int next1 = cur - 1;
		if (cur == 1) {
			break;
		}
		
		if (cur % 3 == 0 && !dp[next3]) {
			dp[next3] = dp[cur] + 1;
			path[next3] = cur;
			q.push(next3);
		}
		if (cur % 2 == 0 && !dp[next2]) {
			dp[next2] = dp[cur] + 1;
			path[next2] = cur;
			q.push(next2);
		}
		if (cur > 1 && !dp[next1]) {
			dp[next1] = dp[cur] + 1;
			path[next1] = cur;
			q.push(next1);
		}
	}
	printf("%d\n", dp[1]); // print shortest path-length
	stack<int> st;
	int x = 1;
	while (x != n) {
		st.push(x);
		x = path[x];
	}
	st.push(x);
    
	// print shortest path
	while (!st.empty()) {
		printf("%d ", st.top());
		st.pop();
	}

	return 0;
}

[유제1 소스코드]

#include <stdio.h>
#include <stack>
using namespace std;

int N;
int list[1001]; // 수열
int best[1001]; // list[x]가 수열의 끝인 최대 길이 저장
int pre[1001]; // best[x]일 때, 그 전 index 저장


int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &list[i]);
		best[i] = 1;
		pre[i] = i;
	}

	for (int i = 1; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (list[i] > list[j] && best[i] < best[j] + 1) {
				best[i] = best[j] + 1;
				pre[i] = j;
			}
		}
	}

	int ans = -1, idx = 0;
	for (int i = 0; i < N; i++) {
		if (ans < best[i]) {
			ans = best[i];
			idx = i;
		}
	}
	printf("%d\n", ans);
	
	stack<int> path;
	while (idx != pre[idx]) {
		path.push(list[idx]);
		idx = pre[idx];
	}
	path.push(list[idx]);

	while (!path.empty()) {
		printf("%d ", path.top());
		path.pop();
	}

	return 0;
}

[유제2 소스코드]

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int a, b;
int visit[10000];

void initVisit() {
	for (int i = 0; i < 10000; i++) {
		visit[i] = 0;
	}
}

void bfs(int n) {
	queue<pair<int, string>> q;
	q.push(make_pair(n, ""));
	visit[n] = 1;

	while (!q.empty()) {
		int cur = q.front().first;
		string str = q.front().second;
		q.pop();

		// BFS 종료 조건 + 정답 출력
		if (cur == b) {
			cout << str << endl;
			break;
		}

		int D, S, L, R;
		D = (2 * cur) % 10000;
		if (cur == 0) S = 9999;
		else S = cur - 1;
		L = (cur % 1000) * 10 + cur / 1000;
		R = (cur % 10) * 1000 + cur / 10;

		if (!visit[D]) {
			q.push(make_pair(D, str + "D"));
			visit[D] = 1;
		}

		if (!visit[S]) {
			q.push(make_pair(S, str + "S"));
			visit[S] = 1;
		}

		if (!visit[L]) {
			q.push(make_pair(L, str + "L"));
			visit[L] = 1;
		}

		if (!visit[R]) {
			q.push(make_pair(R, str + "R"));
			visit[R] = 1;
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	int T;
	scanf("%d", &T);
	while (T--) {
		initVisit();
		scanf("%d %d", &a, &b);
		bfs(a);
	}

	return 0;
}