[BOJ] DSLR

[BOJ] DSLR

Problem URL : DSLR

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

using namespace std;

int tc;
int start;
int goal;

int visited[10000];

int main() {

	scanf("%d", &tc);

	for (int TC = 1; TC <= tc; TC++) {
		string ans = "";
		scanf("%d %d", &start, &goal);
		queue<pair<int, string>> q;

		memset(visited, 0, sizeof(visited));

		q.push({ start,"" });
		visited[start] = 1;

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

			if (n == goal) {
				ans = reg;
				break;
			}

			int dn = (n * 2) % 10000;
			if (!visited[dn]) {
				q.push({ dn, reg + "D" });
				visited[dn] = 1;
			}

			int sn = n - 1;
			if (sn == -1) {
				sn = 9999;
			}
			if (!visited[sn]) {
				q.push({ sn, reg + "S" });
				visited[sn] = 1;
			}

			int ln = (n % 1000) * 10 + (n / 1000);
			if (!visited[ln]) {
				q.push({ ln, reg + "L" });
				visited[ln] = 1;
			}

			int rn = n / 10 + (n % 10) * 1000;
			if (!visited[rn]) {
				q.push({ rn, reg + "R" });
				visited[rn] = 1;
			}
		}
		printf("%s\n", ans.c_str());
	}
	return 0;
}

Comments

cin, cout으로 해주면 속도가 30%가량 느려진다. 그래서 printf, scanf로 했다.