백준 9019 DSLR

https://www.acmicpc.net/problem/9019

9019번: DSLR

 

간단한 구현 문제인데 시간초과가 빡세다... 완전 탐색으로 풀면된다.

 

처음엔 map 자료형과 bfs를 혼합해서 풀었는데 시간초과가 떳다. map 자료형이 시간이 꽤 드는 듯...

 

역시 임의 접근만큼 빠른게 없다. 방문 체크를 할 bool array를 하나 만들어서 작업을 했다. 

 

/* DSLR */

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

void input();
void solve();

int A, B, ANS;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int tt; cin >> tt;
	for (int i = 0; i < tt; i++) {
		input();
		solve();
	}
	return 0;
}

void input() {
	cin >> A >> B;
}

void solve() {
	queue<pair<int, string>> q;
	bool is_visit[10000 + 1] = { false, };

	int result, idx = 0;
	
	q.push({ A, "" });

	while (true) {
		int current = q.front().first;
		string current_instruction = q.front().second;

		q.pop();

		if (current == B) {
			cout << current_instruction << '\n';
			return;
		}

		result = (current * 2 > 9999 ? current * 2 % 10000 : current * 2);

		if (is_visit[result] == false) {
			is_visit[result] = true;
			q.push({ result, current_instruction + 'D' });
		}

		result = (current == 0 ? 9999 : current - 1);
		if(is_visit[result] == false){
			is_visit[result] = true;
			q.push({ result, current_instruction + 'S' });
		}

		result = (current % 1000) * 10 + current / 1000;
		if (is_visit[result] == false) {
			q.push({ result, current_instruction + 'L' });
			is_visit[result] = true;
		}

		result = current % 10 * 1000 + current / 10;
		if(is_visit[result] == false){
			q.push({ result, current_instruction + 'R' });
			is_visit[result] = true;
		}
	}
}