백준 9019: DSLR

문제 요약

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 변환한다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

BFS로 풀면 된다. 큐에서 뽑은 n의 진행 상태를 문자열로 알아야 하므로, 큐는 pair<int, string>이 될 것이다. int부분에는 n을 푸쉬하고, string부분에는 n이 되기까지의 명령어순서를 계속 뒤에 추가하면 된다.

D, S 명령어는 간단하지만, L과 R에서 너무 어렵게 생각하지 않으면 된다.

또 문제를 풀었는지의 여부를 검증하는 bool타입의 sol이란 변수도 사용했었는데, 딱히 사용하지 않아도 성공했다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

queue<pair<int, string>> q;
bool visited[10000];

int main()
{
	int t, a, b, n, temp, d;
	string com;
	cin >> t;
	while (t--) {
		scanf("%d%d", &a, &b);
		q = queue<pair<int, string>>();
		fill_n(visited, 10000, false);
		visited[a] = true;
		q.push({ a, "" });
		while (!q.empty()) {
			n = q.front().first;
			com = q.front().second;
			q.pop();
			if (n == b) break;
			temp = (2 * n) % 10000;
			if (!visited[temp]) {
				q.push({ temp, com + 'D'});
				visited[temp] = true;
			}
			temp = n - 1;
			if (temp < 0) temp = 9999;
			if (!visited[temp]) {
				q.push({ temp, com + 'S' });
				visited[temp] = true;
			}
			d = n / 1000;
			temp = (n - d * 1000) * 10 + d;
			if (!visited[temp]) {
				q.push({ temp, com + 'L' });
				visited[temp] = true;
			}
			d = n % 10;
			temp = (n / 10) + d * 1000;
			if (!visited[temp]) {
				q.push({ temp, com + 'R' });
				visited[temp] = true;
			}
		}
		cout << com << '\n';
	}
	return 0;
}