9019번: DSLR

문제 설명

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

9019번: DSLR

[문제]

  네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
3. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
4. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

  위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

  여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

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

  따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

  n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

 

[입력]

  프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

 

[출력]

  A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

 

[예제 입력 1]

3
1234 3412
1000 1
1 16

[예제 출력 1]

LL
L
DDDD

---

풀이

 문제 자체가 어렵지 않지만, 초반에 어떤 자료구조를 바탕으로 풀어갈 것인가에 따라 정답이 갈렸던 것 같다.

 초반에는 L과 R 명령어를 진행하는데 string 방식이 substr을 이용하여 작성하면 매우 편리할 꺼 같아 전체적인 코드를 string 함수를 기반으로 작성했다. 추가적으로 D와 S 명령어를 진행하면 결과가 4자릿수 미만의 string이 나올 경우 string 자체의 길이가 4보다 짧아질 수 있어, 이를 채워주는 Fill 함수를 추가적으로 작성하여 중간중간 4자리 길이의 string이 유지될 수 있도록 했다. 중복 여부를 확인하는 배열의 경우 string 형태인 숫자를 int로 변환하여 배열의 인덱스로 사용하는 방법을 적용했고, BFS 기반 탐색으로 탐색하는 함수를 작성했다.

 하지만 이렇게 작성한 코드가 알고리즘은 맞았지만, 시간 초과를 피할 수 없었다. 이후 string 관련 연산이 오래 걸린다고 판단하여 기초적인 자료구조와 함수를 모두 int 기반으로 다시 재작성했다. D, S, L, R 명령어들 또한 따로 함수화 하지 않고 BFS 탐색 함수 상에서 바로 계산하여 집어넣었다. 그리고 기존에는 무작정 큐에 넣고 나중에 확인하는 방식을 코드로 작성했지만 이번에는 큐에 넣기 전 미리 확인을 하여 넣는 방식으로 코드를 변경했다.

String 기반 풀이 코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cstring>

using namespace std;

int visited[10000];

string Fill(string s) {
	switch (s.size()) {
	case 1:
		return "000" + s;
	case 2:
		return "00" + s;
	case 3:
		return "0" + s;
	default:
		return s;
	}
}

string D(string s) {
	int n = stoi(s);
	n = (2 * n) % 10000;
	return to_string(n);
}

string S(string s) {
	int n = stoi(s) - 1;
	if (n == -1)
		return "9999";
	else
		return to_string(n);
}

string L(string s) {
	string result = Fill(s);
	return result.substr(1, 3) + result.substr(0, 1);
}

string R(string s) {
	string result = Fill(s);
	return result.substr(3) + result.substr(0, 3);
}

string search(string start, string goal) {
	queue<pair<string, string>> q;
	string ans = "";
	memset(visited, 0, sizeof(visited));
	q.push({ start, "" });

	while (!q.empty()) {
		string reg = q.front().first;
		string route = q.front().second;
		q.pop();

		if (visited[stoi(reg)] == 1) //레지스터 중복이면
			continue;

		if (Fill(reg) == Fill(goal)) {//정답 결과 확인
			ans = route;
			break;
		}

		visited[stoi(reg)] = 1;

		q.push({ D(reg), route + "D" });
		q.push({ S(reg), route + "S" });
		q.push({ L(reg), route + "L" });
		q.push({ R(reg), route + "R" });
	}

	return ans;
}

int main() {
	int T;
	vector<string> answer;
	string start, goal, result;
	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> start >> goal;
		result = search(start, goal);
		answer.push_back(result);
	}

	for (int i = 0; i < T; i++) {
		cout << answer[i] << "\n";
	}

	return 0;
}

int 기반 풀이 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int visited[10000];

string search(int start, int goal) {
	queue<pair<int, string>> q;
	int D, S, L, R;
	string ans;
	memset(visited, 0, sizeof(visited));
	q.push({ start, "" });
	visited[start] = 1;

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

		if (reg == goal) {//정답 확인
			ans = route;
			break;
		}

		D = (reg * 2) % 10000;//명령어 D
		if (visited[D] != 1) {
			visited[D] = 1;
			q.push({ D, route + "D" });
		}

		S = reg - 1;//명령어 S
		if (S == -1)
			S = 9999;
		if (visited[S] != 1) {
			visited[S] = 1;
			q.push({ S, route + "S" });
		}

		L = (reg) % 1000 * 10 + reg / 1000;//명령어 L
		if (visited[L] != 1) {
			visited[L] = 1;
			q.push({ L, route + "L" });
		}

		R = reg / 10 + (reg % 10) * 1000;//명령어 R
		if (visited[R] != 1) {
			visited[R] = 1;
			q.push({ R, route + "R" });
		}
	}

	return ans;
}

int main() {
	int T, start, goal;
	vector<string> answer;
	string result;

	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> start >> goal;
		result = search(start, goal);
		answer.push_back(result);
	}

	for (int i = 0; i < T; i++)
		cout << answer[i] << "\n";

	return 0;
}

---

결과