[BOJ] 백준 9019번: DSLR

www.acmicpc.net/problem/9019

9019번: DSLR

이 문제는 D, S, L, R의 네 가지 명령을 사용해서 주어진 입력 A에서 B를 만드는데 필요한 최소 명령의 수와 그 명령이 무엇인지 출력하는 문제입니다.

D 명령어는 수를 2배하며, S 명령어는 수에 1을 빼는 연산을 수행합니다. 또한 L 명령어는 왼쪽으로 시프트 후 맨 앞자리를 뒤로 위치시키며, R 명령어는 반대로 동작합니다. 아래의 예시를 참고해주세요.

1234 →L 2341 →L 3412
1234 →R 4123 →R 3412

연산을 마친 후, 4자리가 넘어가는 수는 무시하고, 0에서 S 명령을 수행하는 경우는 9999의 연산 결과를 얻습니다. 이를 한번에 처리하기 위하여 mod 10000 연산을 추가로 수행하면 해결할 수 있습니다.

또한, 앞자리 0도 무시합니다. (1000 →R 0100 = 100)

처음 수 A에서 B로 만드는 최소 연산을 구하기 위해 우리는 A->B로 연산의 수를 마치 경로의 개수라고 생각한다면 너비우선탐색 또는 다익스트라 알고리즘과 같은 다양한 최소비용 탐색 알고리즘을 적용할 수 있습니다. 

아래 코드는 큐를 사용한 단순한 BFS와 메모이제이션을 사용한 풀이입니다.

방문 배열을 따로 두지않고 dp 배열을 사용하여 dp[i] = i를 만드는 최소 명령 수, 단 -1 인경우 아직 구하지 않음으로 두었습니다.

또한 어느 명령어를 사용했는지 추적하기 위하여 pre 배열을 선언했습니다. pre[i][0] 은 i를 만들기 위해 이전에 어느 숫자에서 명령을 수행했는지를 의미하며 pre[i][1] 은 어느 명령을 사용했는지를 저장합니다.

아래의 전체 코드를 참고해보세요.

#include <iostream>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <memory.h>
using namespace std;
typedef long long ll;
char ch[4] = { 'D','S','L','R' };
int a, b;
int dp[10001];
int pre[10001][2];
inline int D(int num,int flag) {
	if (flag == 0) {
		return (2 * num);
	}
	if (flag == 1) {
		return (num + 9999);
	}
	if (flag == 2) { // L
		return (num/1000) + (num % 1000)*10;
	}
	return (num % 10) * 1000 + (num / 10);
}
void recv(int num) { // num에서 b를 만드는 최소 연산 횟수 리턴
	queue<pair<int, int> > q;
	q.emplace(0, num);
	while (!q.empty()) {
		int res = q.front().second;
		int turn = q.front().first;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nxt = D(res, i) % 10000;
			if (dp[nxt] == -1) {
				pre[nxt][0] = res;
				pre[nxt][1] = i;
				dp[nxt] = turn + 1;
				if (nxt == b) {
					break;
				}
				q.emplace(dp[nxt], nxt);
			}
		}
	}
	return;
}

void solve() {
	memset(dp, -1, sizeof(dp));
	cin >> a >> b;
	recv(a);
	stack<int> s;
	s.push(pre[b][1]);
	for (int i = pre[b][0]; i != a; i = pre[i][0]) {
		s.push(pre[i][1]);
	}
	while (!s.empty()) {
		cout << ch[s.top()];
		s.pop();
	}
	cout << "\n";
	return;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int t;
	cin >> t;
	for (; t--;) {
		solve();
	}
}