백준 9012 : DSLR

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

1. 접근

• "최소한"의 명령어를 생성한다고 했으므로 최솟값을 구해야 하는데, DFS는 한 길로 쭉 파기 때문에 최솟값, 최댓값을 구하는 문제와는 거리가 멀다.
  => 한번에 한 단계씩 진행하면서, 원하는 값이 나오자마자 바로 종료하게되는 BFS가 최대,최소와 어울리는 경로 탐색 방법이다.
• L과 R의 결과가 무조건 4자리가 나와야 하므로, 굳이 string을 이용할 필요가 없다.(어차피 무조건 4자리씩 확인해야하므로.) => 평소와 같이 숫자로만 접근했다
• BFS 경로탐색을 했을 때, 가장 빨리 목표값을 찾는 건 어렵지 않다.
  ★ 그 값으로 어떻게 가야할지를 아는 것이 어렵다.
  => BT 배열에 (이전값, dslr값) pair를 넣고 마지막에 그 값을 역으로 추적한다.
  ~~=> BT 배열에 각 값의 이전 값을 놓고, 직접 값을 구해 백트랙킹해볼까 했으나.. 2000인 경우, 10002를 해서 2000이 되었는지, 60002을 해서 2000이 나왔는지 알 수 없게 되어 더 복잡해졌다. ~~

2. 반례

1
0 1000
SDDLDSLDRDDD
https://www.acmicpc.net/board/view/65714

3
1 10
775 5421
2784 9034
Output
L
SSSSDL
DSLSLDLL
https://hackids.tistory.com/88

3. 나의 풀이

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

bool visited[10001];
pair<int,int> BT[10001];
char outDSLR[5] = {'0', 'D','S','L','R' };
int a,b;
vector<char> path;

int moveLeft(int val) {
	int num[4];

	for (int i = 3; i >=0; i--) {
		num[i] = val % 10;
		val /= 10;
	}
	for (int i = 0; i < 3; i++) {
		swap(num[i], num[i + 1]);
	}

	int ret = num[0];
	for (int i = 1; i < 4; i++) {
		ret *= 10;
		ret += num[i];
	}
	//cout << ret << "\n";
	return ret;
}

int moveRight(int val) {
	int num[4];

	for (int i = 3; i >= 0; i--) {
		num[i] = val % 10;
		val /= 10;
	}
	for (int i = 3; i >0; i--) {
		swap(num[i], num[i - 1]);
	}

	int ret = num[0];
	for (int i = 1; i < 4; i++) {
		ret *= 10;
		ret += num[i];
	}
	//cout << ret << "\n";
	return ret;
}


void BFS(int start) {
	queue<int> q;

	q.push(start);
	BT[start]=make_pair(start,0);
	visited[start] = true;

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

		if (now == b) {
			return;
		}
		int dslr[5];
		dslr[1] = (now * 2) % 10000;

		dslr[2] =now- 1;
		if (dslr[2] < 0)	dslr[2] = 9999;
		dslr[3] = moveLeft(now);
		dslr[4] = moveRight(now);

		for (int i = 1; i < 5; i++) {
			if (!visited[dslr[i]]) {
				visited[dslr[i]]=true;
				BT[dslr[i]]=make_pair(now,i);
				q.push(dslr[i]);
			}
		}
		
	}
}

void backtracking(int start) {
	if (start == a)	return;

	path.push_back(outDSLR[BT[start].second]);
	backtracking(BT[start].first);

	return;
}

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

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

		memset(visited, false, sizeof(visited));
		path.clear();
		BFS(a);
		backtracking(b);

		for (int i = path.size() - 1; i >= 0; i--) {
			cout << path[i];
		}
		cout << "\n";
	}

	return 0;
}

BFS만 떠올렸다면 방향을 잡기는 쉬웠겠지만 경로 출력하게하는부분이 어려웠다..