[BOJ] 9019번_DSLR_BFS (C++)

[문제]

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

D,S,L,R 이라는 4개의 명령어를 가진 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0부터 9999까지의 십진수를 저장할 수 있다. 각 명령어는 다음과 같은 역할을 수행한다.

D : n을 두 배로 바꾼다. 결과 값이 9999보다 큰 경우에는 10000으로 나눈 나머지를 취한다. 그 후 결과를레지스터에 저장한다. ex) 1234 -> 2468
S : n에서 1을 뺀 결과를 레지스터에 저장한다. n이 0이면 9999가 대신 레지스터에 저장된다. ex) 1234 -> 1233
L : n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. ex) 1234 -> 2341
R : n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. ex) 1234 -> 4123

위와 같은 명령어를 가진 계산기로 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램을 만드는 문제이다.

[사용 알고리즘]

BFS(너비 우선 탐색)

[풀이 핵심]

• 간단하게 설명하면 DSLR을 전부 가중치를 1이라고 생각했을 때 가장 낮은 가중치로 목적지에 도달하는 방법을 구하는 문제이다. 때문에 BFS로 탐색하면 쉽게 구할 수 있다.
• 1000을 L계산 했을 때 0001이 아니라 1이 되어야 하므로, string이 아닌 int형으로 해결하는 것이 낫다.
• visited[] 배열을 이용하여 지금까지 결과값으로 나왔던 값은 탐색하지 않았다. (2번 째로 방문하면 1번째로 방문했을 때보다 가중치의 합이 높기 때문)

[코드]

//boj9019번_DSLR_그래프

#include<iostream>
#include<queue>

using namespace std;

int A, B;

bool visited[10001];

void BFS() {
	queue<pair<int, string>> q;
	q.push({ A,"" });
	visited[A] = true;

	while (!q.empty()) {
		int x = q.front().first;
		string s = q.front().second;
		q.pop();

		if (x == B) {
			cout << s << '\n';
			return;
		}

		int D = (2 * x) % 10000;

		if (!visited[D]) {
			visited[D] = true;
			q.push({ D,s + "D" });
		}

		int S;
		if (x == 0) {
			S = 9999;
		}
		else {
			S = x - 1;
		}

		if (!visited[S]) {
			visited[S] = true;
			q.push({ S,s + "S" });
		}

		int L = ((x % 1000) * 10) + (x / 1000);

		if (!visited[L]) {
			visited[L] = true;
			q.push({ L,s + "L" });
		}

		int R = (x / 10) + ((x % 10) * 1000);

		if (!visited[R]) {
			visited[R] = true;
			q.push({ R,s + "R" });
		}
	}
}

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

	for (int i = 0; i < T; i++) {
		cin >> A >> B;

		for (int j = 0; j < 10001; j++) {
			visited[j] = false;
		}

		BFS();
	}

	return 0;
}