BOJ-9019 DSLR

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

문제 소개

테스트 케이스의 개수 T가 주어지고 각 테스트 케이스마다 두 개의 정수 A와 B가 주어진다.

네 개의 명령어 D, S, L, R을 이용하여 정수 A를 B로 변환하는 최소한의 명령어 나열을 구한다.

정수 n에 대한 각 명령어의 효과는 아래와 같다.

1. D : n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다.(2n mod 10000)
2. S : n - 1을 레지스터에 저장한다. n이 0 이라면 9999가 된다.
3. L : n의 각 자릿수를 왼편으로 회전시킨다.
4. R : n의 각 자릿수를 오른편으로 회전시킨다.

문제 풀이

bfs로 풀이하였다. 큐 q의 원소는 pair<int, string>의 형태를 가지는데, [n, n까지 도달하기 위한 연산]의 의미이다.

current_num(현재 수)에 대한 4가지 연산의 결과값인 t를 연산 후 visited(방문 여부)를 확인하여 방문하지 않았다면 q에 push하고 방문 처리한다.

만약 t가 목표값인 B와 일치한다면 누적된 연산을 출력하고 break한다.

L과 R 명령어는 나누기와 나머지 연산을 이용하여 구현하였다.

각 테스트 케이스가 끝난 후에는 전역으로 선언된 visited를 memset으로 다시 초기화해주었다.

코드

#include <iostream>
#include <string>
#include <queue>
#include <memory.h>

bool visited[10000] = { false };

void bfs(int start, int target) {
	std::queue<std::pair<int, std::string>> q;
	q.push({ start, "" });
	visited[start] = true;
	while (!q.empty()) {
		int current_num = q.front().first;
		std::string current_op = q.front().second;
		q.pop();

		int t;

		// D
		t = current_num * 2 % 10000;
		if (!visited[t]) {
			if (t == target) {
				std::cout << current_op + "D" << "\n";
				break;
			}
			q.push({ t, current_op + "D" });
			visited[t] = true;
		}

		// S
		if (current_num == 0) {
			t = 9999;
		}
		else {
			t = current_num - 1;
		}
		if (!visited[t]) {
			if (t == target) {
				std::cout << current_op + "S" << "\n";
				break;
			}
			q.push({ t, current_op + "S" });
			visited[t] = true;
		}

		// L
		t = current_num % 1000 * 10 + current_num / 1000;
		if (!visited[t]) {
			if (t == target) {
				std::cout << current_op + "L" << "\n";
				break;
			}
			q.push({ t, current_op + "L" });
			visited[t] = true;
		}

		// R
		t = current_num % 10 * 1000 + current_num / 10;
		if (!visited[t]) {
			if (t == target) {
				std::cout << current_op + "R" << "\n";
				break;
			}
			q.push({ t, current_op + "R" });
			visited[t] = true;
		}
	}
}

int main() {
	using namespace std;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int t;
	cin >> t;
	while (t--) {
		int a, b;
		cin >> a >> b;
		bfs(a, b);
		memset(visited, false, sizeof(visited));
	}

	return 0;
}