백준 9019_DSLR

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

9019번: DSLR

D: N -> 2*N, S: N -> N-1, L: Shift Left, R: Shift Right 으로 주어졌을 때,

위 4 연산을 활용하여 네 자리 숫자 A -> B 바꾸는 최소 연산 과정을 출력하는 문제이다.

 

가중치가 동일하고 정점과 간선 수가 많지 않으며 최소탐색을 찾는 문제이기에 BFS를 활용하여 해결할 수 있다.

char from_ch[idx]를 통해 어떤식으로 만들어 왔는지
int from[idx]를 통해 어디서 왔는지(경로)

를 기록하면서 BFS로 탐색한다. 

각각의 연산마다 If문 통해 처리하기!
L : next = (now%1000)*10 + (now/1000)
R : next = (now/10) + (now%10)*1000

 

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

int main() {
	int t;
	cin >> t;

	// t번 반복
	for (int i = 0; i < t; i++) {
		vector<int> from(10000, 0);
		vector<char> from_ch(10000, 0);
		vector<bool> check(10000, false);
		queue<int> q;
		int a, b;

		cin >> a >> b;
		check[a] = true, q.push(a);
		// BFS
		while (!q.empty()) {
			int now_a = q.front();
			q.pop();

			// D (안 갔으면)
			int next = (now_a * 2) % 10000;
			if (!check[next]) {
				from[next] = now_a;
				from_ch[next] = 'D';
				check[next] = true;
				q.push(next);
			}

			// S
			next = now_a - 1;
			if (now_a == 0)
				next = 9999;
			if (!check[next]) {
				from[next] = now_a;
				from_ch[next] = 'S';
				check[next] = true;
				q.push(next);
			}

			// L
			int next_l = (now_a % 1000) * 10 + now_a / 1000;
			if (!check[next_l]) {
				from[next_l] = now_a;
				from_ch[next_l] = 'L';
				check[next_l] = true;
				q.push(next_l);
			}

			// R
			int next_r = (now_a / 10) + (now_a % 10) * 1000;
			if (!check[next_r]) {
				from[next_r] = now_a;
				from_ch[next_r] = 'R';
				check[next_r] = true;
				q.push(next_r);
			}
		}

		// 경로 추적
		vector<char> path;
		int tr = b;
		while (tr != a) {
			path.push_back(from_ch[tr]);
			tr = from[tr];
		}
		reverse(path.begin(), path.end());

		// 경로 출력
		for (int j = 0; j < path.size(); j++)
			cout << path[j];
		cout << endl;

	}
}