백준 9019번 DSLR C++

출처 : https://www.acmicpc.net/problem/9019

 

a에서 b로 변환되는 경우를 bfs를 통해 탐색하였고, 탐색하는 과정에서 parent벡터를 만들어서 어떤 수에서 어떤 레지스터를 사용해서 값이 나왔는지를 저장하였다.

 

탐색이 끝났을 때 parent벡터를 이용해 역추적해서 사용된 레지스터들을 알아낼 수 있다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int Register(int num, int val) {
	int ret;
	int tmp;
	switch (num) {
	case 0:
		ret = (val * 2) % 10000;
		break;
	case 1:
		ret = val - 1;
		if (val == 0) ret = 9999;
		break;
	case 2:
		tmp = val / 1000;
		val = (val * 10) % 10000;
		ret = val + tmp;
		break;
	case 3:
		tmp = val - ((val / 10) * 10);
		val = val / 10;
		ret = val + tmp * 1000;
		break;
	default:
		ret = -1;
		break;
	}
	return ret;
}

void bfs(int start, int target) {
	vector<bool> found(10000, false);
	vector<pair<int, int>> parent(10000, { 0,-1 });
	queue<int> q;
	int idx;

	q.push(start);
	found[start] = true;
	parent[start] = { start,4 };

	while (!q.empty()) {
		int curr = q.front();
		if (curr == target) {
			idx = curr;
			break;
		}
		q.pop();
		for (int i = 0; i < 4; i++) {
			int next = Register(i, curr);
			if (found[next]) continue;
			q.push(next);
			found[next] = true;
			parent[next] = { curr,i };
		}
	}
	vector<int> ans;
	while (parent[idx].first != idx) {
		ans.push_back(parent[idx].second);
		idx = parent[idx].first;
	}
	for (int i = ans.size() - 1; i >= 0; i--) {
		switch (ans[i]) {
		case 0:
			cout << 'D';
			break;
		case 1:
			cout << 'S';
			break;
		case 2:
			cout << 'L';
			break;
		case 3:
			cout << 'R';
			break;
		default:
			break;
		}
	}
	cout << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t, a, b;
	cin >> t;
	while (t--) {
		cin >> a >> b;
		bfs(a, b);
	}
};