9019번

4개의 숫자를 순서대로 4자리의 숫자로 만드는데, 이 4개의 숫자를 다음 4개의 명령어를 이용해 가장 짧은 방법으로 목표에 도달하는 것을 목적으로 하는 문제이다. 명령어는 다음과 같다.
1. D - 현재 N을 두배로 만든다. (단! 10000이 넘어가면 모듈러 연산을 한다.)
2. S - 현재 N에서 1을 감소시킨다. (단! n이 0일경우 -1대신 9999를 반환한다.)
3. L - 현재 N의 숫자를 왼쪽으로 한칸씩밀고 제일 앞 숫자를 0번쨰 자리에 위치한다.
4. R - 현재 N의 숫자를 오른쪽으로 한칸씩밀고 0번쨰 자리 숫자를 3번째 칸에 위치시킨다.

이 문제에서 중요한것은 4개의 숫자를 이용한다는 것이다.
예를 들어 4개의 숫자가 각각 1234라 한다면 당연하게도 다음과 같다.

L연산 - 2341
R연산 - 4123

하지만 4개의 숫자가 0016이라면?

L연산 - 0160
R연산 - 6001

입력이 0016대신 16으로 주어지기에 주의할 필요가 있는 문제였다.
각 명령어 별로 다른 숫자에 도달하기 때문에 BFS를 이용하여 문제를 풀었다.
정답코드

#include <iostream>

using namespace std;

struct st {
	int n;
	string ans;
};

st arr[40001];
st temp[40001];
bool visit[10001];

int funcD(int n) {
	return (n * 2) % 10000;
}

int funcS(int n) {
	if (n != 0)
		return n - 1;
	else
		return 9999;
}

int funcL(int n) {
	int a, b, c, d;
	a = (n % 10000) / 1000;
	b = (n % 1000) / 100;
	c = (n % 100) / 10;
	d = n % 10;
	return b*1000+c*100+d*10+a;
}

int funcR(int n) {
	int a, b, c, d;
	a = (n % 10000) / 1000;
	b = (n % 1000) / 100;
	c = (n % 100) / 10;
	d = n % 10;
	return d*1000+a*100+b*10+c;
}

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

void find_answer(int origin,int answer) {
	set0();
	int j, k = 1;
	bool flag = 0;
	arr[0].n = origin;
	arr[0].ans = "";
	visit[arr[0].n] = 1;
	while (k!=0) {
		j = k;
		k = 0;
		for (int i = 0; i < j; i++) {
			if (arr[i].n == answer) {
				cout << arr[i].ans << '\n';
				return;
			}
			int a = funcD(arr[i].n);
			if (!visit[a]) {
				visit[a] = 1;
				temp[k].n = a;
				temp[k++].ans = arr[i].ans + "D";
			}
			a = funcS(arr[i].n);
			if (!visit[a]){
				visit[a] = 1;
				temp[k].n = a;
				temp[k++].ans = arr[i].ans + "S";
			}
			a = funcL(arr[i].n);
			if (!visit[a]) {
				visit[a] = 1;
				temp[k].n = a;
				temp[k++].ans = arr[i].ans + "L";
			}
			a = funcR(arr[i].n);
			if (!visit[a]) {
				visit[a] = 1;
				temp[k].n = a;
				temp[k++].ans = arr[i].ans + "R";
			}
		}
		for (int i = 0; i < k; i++) {
			arr[i] = temp[i];
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int origin, answer;
		cin >> origin >> answer;
		find_answer(origin, answer);
	}

	return 0;
}