(c++)백준 9019번: DSLR

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

9019번: DSLR

[풀이]

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력하는 문제이므로 bfs를 사용했다.

DSLR연산을 각각 한 상태를 queue에 집어넣고 B가 나오면 그때까지 사용했던 연산 문자열을 반환했다.

 

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

struct Value {
	int n;
	string s;
};

int T;
int A, B;
bool check[10000];

string bfs() {
	queue<Value>q;
	q.push({ A,"" });
	check[A] = true;

	while (!q.empty()) {
		int n = q.front().n;
		string s = q.front().s;
		q.pop();
		if (n == B)return s;

		//D
		int nn = n * 2;
		if (nn > 9999)nn = nn % 10000;
		if (check[nn] == false) {
			check[nn] = true;
			q.push({ nn,s + 'D' });
		}

		//S
		nn = n - 1;
		if (nn < 0)nn = 9999;
		if (check[nn] == false) {
			check[nn] = true;
			q.push({ nn,s + 'S' });
		}

		//L
		nn = (n % 1000) * 10 + (n / 1000);
		if (check[nn] == false) {
			check[nn] = true;
			q.push({ nn,s + 'L' });
		}

		//R
		nn = (n % 10) * 1000 + (n / 10);
		if (check[nn] == false) {
			check[nn] = true;
			q.push({ nn,s + 'R' });
		}
	}
}

int main() {
	cin >> T;
	while (T--) {
		memset(check, false, sizeof(check));
		cin >> A >> B;
		cout << bfs() << '\n';
	}
	return 0;
}