[백준] 9019-DSLR

문제링크: https://www.acmicpc.net/problem/9019

9019번: DSLR

 

BFS를 사용하여 해결하는 문제였습니다. 

수의 범위가 0 이상 10,000 미만의 십진수이기 때문에 visited 배열을 만들어서 방문 했던 값을 표시하면서 시간을 확보 했습니다. queue를 pair로 사용해서 int, string 함께 저장하여 해결하였습니다. 

 

string을 쓰지않고 char형 만으로 구현하는게 베스트인 문제입니다! (사실 string을 사용하면 시간초과가 나게끔 유도한 느낌의 문제였습니다.. ㅠㅠ) 

 

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

int t = 0;
int a = 0, b = 0;
bool visited[10000];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> t;

	string result;

	while (t--) {
		memset(visited, 0, sizeof(visited));

		result = "";

		cin >> a >> b;
		queue <pair<int, string>> que;
		// 0 -> D 1 -> S 2 -> L 3 -> R
		que.push(make_pair(a, ""));
		visited[a] = 1;
		string word;
		while (!que.empty()) {

			int num = que.front().first;
			word = que.front().second;
			que.pop();
			
			if (num == b) {
				result = word;
				break;
			}

			int verifed_num = (num * 2) % 10000;
			if(!visited[verifed_num])
				que.push(make_pair(verifed_num, word + "D")), visited[verifed_num] = 1;
			
			if (num == 0 && !visited[9999]) que.push(make_pair(9999, word + "S")), visited[9999] = 1;
			else if(!visited[num - 1])que.push(make_pair(num - 1, word + "S")), visited[num - 1] = 1;
			
			verifed_num = (num % 1000) * 10 + (num / 1000);
			if (!visited[verifed_num])
				que.push(make_pair(verifed_num, word + "L")), visited[verifed_num] = 1;
			verifed_num = (num / 10) + (num % 10) * 1000;
			if (!visited[verifed_num])
				que.push(make_pair(verifed_num, word + "R")), visited[verifed_num] = 1;

		}

		cout << result << "\n";
	}

}