[백준/C++] 9019. DSLR

문제

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

 

풀이

BFS를 이용했다.

가능한 경우의 수가 0 ~ 9999 까지 였기 때문에, 10000크기의 visited 배열을 만들어 이용했다.

 

처음에 L과 R을 숫자를 String으로 바꾸어서 만드는 방식으로 해서 시간초과가 나왔다. 

굉장히 사소한 부분이라고 생각했는데, 테스트케이스를 많이 집어넣을 수 있는 방식이라서 시간초과가 난 것 같다.

 

그리고 main에 cin, cout 입출력 시간을 줄이기 위한 코드를 추가했더니 시간이 아주 조금 더 줄었다. 

 

코드

#include <iostream>
#include <queue>
#include <string>
using namespace std;

#define MAX 10000

bool visited[MAX];
string BFS(int A, int B) {
	queue<pair<int, string>> q;
	q.push(make_pair(A, ""));

	//string Bs = intToString(B);
	while (!q.empty()) {
		int num = q.front().first;
		string commend = q.front().second;
		q.pop();
		// D
		int D = (num * 2) % MAX;
		if (!visited[D]) {
			visited[D] = 1;
			q.push(make_pair(D, commend + 'D'));
			if (D == B) return commend + 'D';
		}
		// S
		int S = num - 1;
		if (S < 0) S = MAX - 1;
		if (!visited[S]) {
			visited[S] = 1;
			q.push(make_pair(S, commend + 'S'));
			if (S == B) return commend + 'S';
		}
		// L
		int L = (num * 10) % 10000 + num / 1000;
		if (!visited[L]) {
			visited[L] = 1;
			q.push(make_pair(L, commend + 'L'));
			if (L == B) return commend + 'L';
		}
		// R
		int R = (num / 10) + (num % 10) * 1000;
		if (!visited[R]) {
			visited[R] = 1;
			q.push(make_pair(R, commend + 'R'));
			if (R == B) return commend + 'R';
		}
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int T;
	cin >> T;
	for (int t = 0;t < T;t++) {
		fill(&visited[0], &visited[MAX], 0);
		int A, B;
		cin >> A >> B;
		string result = BFS(A, B);
		cout << result << endl;
	}
	return 0;
}

결과