[백준/BOJ] 백준 9019번 : DSLR

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

9019번: DSLR

 

초기값에서 bfs(너비 우선 탐색)을 통해 최종 값으로 가는 최소한의 명령어를 구했다.

 

코드

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

int t;
string a, b;
vector<string> output;

string solve(int a, int b) {
	vector<string> discovered(10005, "-1");
	queue<int> q;

	q.push(a);
	discovered[a] = "";

	while (!q.empty()) {
		int here = q.front();
		q.pop();

		if (here == b) {
			return discovered[b];
		}

		int there;

		//D를 수행할때
		there = (here * 2) % 10000;
		if (discovered[there] == "-1") {
			discovered[there] = discovered[here] + "D";
			q.push(there);
		}

		//S를 수행할때
		there = here - 1;
		if (there < 0) {
			there = 9999;
		}
		if (discovered[there] == "-1") {
			discovered[there] = discovered[here] + "S";
			q.push(there);
		}

		//L을 수행할때
		there = ((here % 1000) * 10) + (here / 1000);
		if (discovered[there] == "-1") {
			discovered[there] = discovered[here] + "L";
			q.push(there);
		}

		//R을 수행할때
		there = ((here % 10) * 1000) + (here / 10);
		if (discovered[there] == "-1") {
			discovered[there] = discovered[here] + "R";
			q.push(there);
		}
	}

	return "-1";
}

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

	cin >> t;

	for (int tc = 0; tc < t; tc++) {
		int a, b;
		cin >> a >> b;

		string result = solve(a, b);
		output.push_back(result);
	}

	for (int i = 0; i < output.size(); i++) {
		cout << output[i] << "\n";
	}

	return 0;
}