백준 9019번 C++

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

using namespace std;
const int MAX = 10001;
const int MOD = 10000;
int visited[MAX];

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

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

		if (current == end) {
			cout << cmd << endl;
			return;
		}

		int movenum = (current * 2) % MOD;
		if (visited[movenum] == -1) {
			visited[movenum] = 1;
			q.push(make_pair(movenum,cmd + "D"));
		}
		
		movenum = (current - 1) < 0 ? 9999 : current - 1;
		if (visited[movenum] == -1) {
			visited[movenum] = 1;
			q.push(make_pair(movenum, cmd + "S"));
		}

		movenum = (current % 1000) * 10 + (current / 1000);
		if (visited[movenum] == -1) {
			visited[movenum] = 1;
			q.push(make_pair(movenum, cmd + "L"));
		}

		movenum = (current % 10) * 1000 + (current / 10);
		if (visited[movenum] == -1) {
			visited[movenum] = 1;
			q.push(make_pair(movenum, cmd + "R"));
		}
	}
}

int main(void) {
	int testcase;
	int a, b;

	cin >> testcase;
	for (int i = 0; i < testcase; i++) {
		memset(visited, -1, sizeof(visited));
		cin >> a >> b;
		bfs(a, b);
	}
	return 0;
}