[백준] 9019번 DSLR

9019번: DSLR

D, S, L, R 각 경우에 맞게 값을 변형시킨 다음

그 값이 될 때까지 어떤 과정이 있었는지 배열에 저장한 뒤

그 값이 B가 되면 출력하면 된다.

 

여기서 주의할 점은 네 자리 레지스터라서

'L 적용 시 123이니까 231이겠지'라고 생각하면 안 된다.

123은 0123으로 취급하여 L 적용 시 1230이 된다.

 

처음에 잘못 생각하고  string으로 복잡하게 변형시켜주다 시간 초과 걸렸었다.

이 점만 주의해주면 굳이 string 쓸 필요 없이 계산으로 변형 가능하다.

#include <iostream>
#include <queue>
#include <string>
using namespace std;
int num, temp;

void Bfs(int B, string res[], bool visited[], queue <int> q) {
	while (!q.empty()) {
		if (q.front() == B) break;

		num = 2 * q.front() % 10000;
		if (!visited[num]) {
			res[num] = res[q.front()] + "D";
			if (num == B) break;
			q.push(num);
			visited[num] = true;
		}

		if (q.front() == 0) num = 9999;
		else num = q.front() - 1;
		if (!visited[num]) {
			res[num] = res[q.front()] + "S";
			if (num == B) break;
			q.push(num);
			visited[num] = true;
		}

		temp = q.front() / 1000;
		num = q.front() % 1000;
		num = num * 10 + temp;
		if (!visited[num]) {
			res[num] = res[q.front()] + "L";
			if (num == B) break;
			q.push(num);
			visited[num] = true;
		}

		temp = q.front() / 10;
		num = q.front() % 10;
		num = num * 1000 + temp;
		if (!visited[num]) {
			res[num] = res[q.front()] + "R";
			if (num == B) break;
			q.push(num);
			visited[num] = true;
		}

		q.pop();
	}
}

int main() {
	int T, A, B;
	cin >> T;
	for (int t = 0; t < T; t++) {
		cin >> A >> B;
		queue <int> q;
		q.push(A);
		bool visited[10001] = { false };
		visited[A] = true;
		string res[10001];
		Bfs(B, res, visited, q);
		cout << res[B] << "\n";
	}

	return 0;
}