[백준] 9019번 DSLR C++ 풀이

---

알고리즘 분류

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

---

문제 설명

네 개의 명령어 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로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

---

예제 입력

3
1234 3412
1000 1
1 16

---

예제 출력

LL
L
DDDD

---

아이디어

입력받은 숫자에서부터 시작해서 목표하는 숫자에 도달할 때까지 DSLR 중 가능한 명령어를 모두 실행하여 바뀐 숫자에 방문한 적이 없다면 지금까지 실행한 명령어와 함께 바뀐 숫자를 방문한 것으로 기록한다. 그러다가 목표하는 숫자에 도달하면 지금까지 실행한 명령어를 출력한다. BFS이므로 가장 먼저 도달하는 명령어가 가장 짧은 명령어이다.

---

알고리즘

시작하는 숫자에서부터 목표 숫자에 도달할 때까지 현재 숫자가 범위 내에 있다면 방문 표시를 하고 queue에 넣으면서 각 명령어를 실행하고 지금까지 실행한 명령어를 저장한다.

목표 숫자에 도달했다면 지금까지 실행한 명령어를 출력하고 종료한다.

---

코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
void BFS(int bef, int aft)
{
	vector<bool> vec(10001,0);
	queue<pair<int,string>> q;
	q.push({bef,""});
	vec[bef] = 1;
	while(!q.empty())
	{
		int curnum = q.front().first,temp,f;
		string curstr = q.front().second;
		q.pop();
		if(0<curnum && curnum<10000)
		{
			temp = curnum;
			temp = (temp << 1) % 10000;
			if(vec[temp] == 0)
			{
				vec[temp] = 1;
				q.push({temp, curstr+"D"});
				if(temp == aft)
				{
					cout<<curstr+"D\n";
					break;
				}
			}
		}

		if(0<=curnum && curnum<10000)
		{
		    if(curnum == 0) temp = 9999;
			else temp = curnum-1;
			if(temp < 0) temp = 9999;
			if(vec[temp] == 0)
			{
				vec[temp] = 1;
				q.push({temp, curstr+"S"});
				if(temp == aft)
				{
					cout<<curstr+"S\n";
					break;
				}
			}
		}

		if(0<curnum && curnum<10000)
		{
			f = curnum/1000;
			temp = (curnum%1000)*10+f;
			if(vec[temp] == 0)
			{
				vec[temp] = 1;
				q.push({temp, curstr+"L"});
				if(temp == aft)
				{
					cout<<curstr+"L\n";
					break;
				}
			}
		}

		if(0<curnum && curnum<10000)
		{
			f = curnum%10;
			temp = (curnum-f)/10+f*1000;
			if(vec[temp] == 0)
			{
				vec[temp] = 1;
				q.push({temp, curstr+"R"});
				if(temp == aft)
				{
					cout<<curstr+"R\n";
					break;
				}
			}
		}
	}

}
int main()
{
	int T; cin>>T;
	while(T--)
	{
		int bef, aft;
		cin>>bef>>aft;
		BFS(bef,aft);
	}
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/9019

처음에는 BFS를 생각하지 못했다. 그래서 LLLL, RRRR 등등부터 하나씩 하면서 찾는 방법을 시도했다.

하지만 이런 방식은 LDRS같은 복잡한 명령어를 찾아내기 힘들었다.

그래서 BFS로 방식을 바꿨다. 3%에서 계속 틀려서 짜증났는데 목표 숫자를 0으로 놓는 테스트 케이스를 통해서 해결했다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!