#9019. DSLR

Problem

• 문제링크

Solution

• 이 문제는 명령어 ‘L’과 ‘R’을 어떻게 수행하느냐가 제일 중요하다.
• 처음에 deque를 사용하여 숫자를 배열로 나누고 합치고 이러다가 시간초과…
• 사실 사칙연산만 사용하면 위 명령어를 수행할 수 있다.
• L 명령어

Next = (Now % 1000 * 10) + (Now / 1000)

• R 명령어

Next = (Now / 10) + (Now % 10 * 1000)

• 주의해야 할 사항

테스트 케이스를 여러 번 수행하는 문제이므로 초기화가 필요한 변수나 배열은 초기화를 해줘야 한다.

명령어를 저장하고 있어야 하므로, 해당 숫자를 어떻게 만들었는지 경로를 저장할 배열을, 그 숫자를 만들 때 쓴 명령어가 무엇인지 저장할 배열을 만든다.

from[a] = b a를 만들기 이전 숫자 b

how[a] = 'b' a를 만들 때 수행된 명령어 b

1 Try

• code

  #include <iostream>
  #include <queue>
  #include <deque>
  #include <vector>
  #include <cstring>
  #define MAX 10000
  using namespace std;
  char cmd[4] = { 'D', 'S', 'L', 'R' };
  bool check[MAX];
  int from[MAX];
  char how[MAX];
  int A, B;
  void Init() {
  	memset(check, 0, sizeof(check));
  }
  void PrintCmd(int a, int b) {
  	if (a != b) {
  		PrintCmd(a, from[b]);
  		cout << how[b];
  	}	
  }
  void BFS() {
  	queue<int> q;
  	q.push(A);
  	check[A] = true;
  	while (!q.empty()) {
  		int a = q.front();
  		q.pop();
  		if (a == B) {
  			PrintCmd(A, B);
  			cout << "\n";
  			return;
  		}
  		int d = a * 2 > MAX - 1 ? a * 2 % MAX : a * 2;
  		if (!check[d]) {
  			check[d] = true;
  			how[d] = 'D';
  			from[d] = a;
  			q.push(d);
  		}
  		int s = a == 0 ? MAX - 1 : a - 1;
  		if (!check[s]) {
  			check[s] = true;
  			how[s] = 'D';
  			from[s] = a;
  			q.push(s);
  		}
  		int cur = a;
  		deque<int> ld, rd;
  		for (int i = 0, div = 1000; i < 4; ++i, div /= 10) {
  			int num = cur / div; cur %= div;
  			ld.push_back(num); rd.push_back(num);
  		}
  		int tmp = ld.front(); ld.pop_front();
  		ld.push_back(tmp);
  		tmp = rd.back(); rd.pop_back();
  		rd.push_front(tmp);
  		int l = 0, r = 0;
  		for (int i = 0, div = 1; i < 4; ++i, div *= 10) {
  			l += ld.back() * div;
  			r += rd.back() * div;
  			ld.pop_back(); rd.pop_back();
  		}
  		if (!check[l]) {
  			check[l] = true;
  			how[l] = 'L';
  			from[l] = a;
  			q.push(l);
  		}
  		if (!check[r]) {
  			check[r] = true;
  			how[r] = 'R';
  			from[r] = a;
  			q.push(r);
  		}
  	}
  }
  int main() {
  	int T;
  	cin >> T;
  	for (int t = 0; t < T; ++t) {
  		Init();
  		cin >> A >> B;
  		BFS();
  	}
  	return 0;
  }

  시간초과

2 Try

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 10000
using namespace std;
char cmd[4] = { 'D', 'S', 'L', 'R' };
bool check[MAX];
int from[MAX];
char how[MAX];
int A, B;
void Init() {
	memset(check, 0, sizeof(check));
}
void PrintCmd(int a, int b) {
	if (a != b) {
		PrintCmd(a, from[b]);
		cout << how[b];
	}	
}
void BFS() {
	queue<int> q;
	q.push(A);
	check[A] = true;
	while (!q.empty()) {
		int a = q.front();
		q.pop();
		if (a == B) {
			PrintCmd(A, B);
			cout << "\n";
			return;
		}
		int d = a * 2 % MAX;
		if (!check[d]) {
			check[d] = true;
			how[d] = 'D';
			from[d] = a;
			q.push(d);
		}
		int s = a == 0 ? MAX - 1 : a - 1;
		if (!check[s]) {
			check[s] = true;
			how[s] = 'S';
			from[s] = a;
			q.push(s);
		}
		int l = (a % 1000 * 10) + (a / 1000);
		if (!check[l]) {
			check[l] = true;
			how[l] = 'L';
			from[l] = a;
			q.push(l);
		}
		int r = (a / 10) + (a % 10 * 1000);
		if (!check[r]) {
			check[r] = true;
			how[r] = 'R';
			from[r] = a;
			q.push(r);
		}
	}
}
int main() {
	int T;
	cin >> T;
	for (int t = 0; t < T; ++t) {
		Init();
		cin >> A >> B;
		BFS();
	}
	return 0;
}