[백준/알고리즘] 9019번 DSLR (골드 5)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 9019번

 

정수 A, B와 D, S, L, R을 이용하는 간단한 계산기가 있다. 계산기에는 0이상 10000미만의 십진수를 저장하는 하나의 레지스터가 있다.
정수 A를 B와 같게 만들도록 하는 연산 순서를 출력하시오. 연산은 다음과 같다.

 

백준 9019번 문제 설명

 

풀이 알고리즘 : BFS

 

일단 시작하기에 앞서, 문제의 시간제한은 6초지만, TC가 많이 들어올 수 있기 때문에, 시간제한에 유의해야한다.

 

이전 소수경로 문제와 비슷하게, BFS를 이용하여 모든 숫자를 확인하면, BFS의 특성상 깊이(이동 횟수)가 같기 때문에, 가장 먼저 A가 B와 같아지는 경우가 최단 경로이다.

 

배열에서 좌표를 변환하는 것 대신, 이 문제에서는 4가지 연산이 추가되었는데, 각각 수식으로 표현이 가능하다.

 

i는 현재 확인하고 있는 숫자이고, next는 다음에 확인해야 할 숫자라고 가정하자.

 

D연산은 문제에서 나와있는데로 next = (i * 2) % 10000 이다.

S연산은 마찬가지로 n이 0인 경우를 따로 처리해줘서 next = ((i == 0) ? 9999 : i - 1) 이다.

L연산은 가장 앞에있는 숫자를 맨 뒤로, 나머지 숫자들을 왼쪽으로 이동시키는 연산인데, next = (i / 1000) + (i % 1000) * 10 으로 표현 가능하다.

R연산은 반대로 가장 뒤의 숫자를 맨 앞으로, 나머지 숫자들을 오른쪽으로 이동시킨다. 즉, next = (i % 10) * 1000 + (i / 10) 이다.

 

앞에서 유의한대로, 만약 4가지 연산 중, string 형으로 연산을 구현하여서 string의 복사 등의 이유로 시간이 느려지거나 하면 시간초과에 걸릴 수 있음에 유의하자.

 

그리고 각각의 연산으로 next를 구한 다음에, 확인하지 않은 숫자라면 확인해서, BFS를 계속 탐색한다.

 

이때, 연산 횟수를 최소로 줄이기 위해서 if문에 들어가면, 두가지 확인을 해야한다.

 

첫번째는 next가 b라면, 현재까지의 연산 + 이번에 시행한 연산을 출력하고 반복을 멈춰야 한다.

두번째는 check배열을 true로 초기화해야한다.

 

두 과정 모두 중복되는 처리를 최소한으로 하기 위해서 처리해주는 것이 좋다.

이후 TC마다 공백이 하나씩 출력해야 함을 유의하면서 코드를 구현하였다.

 

소스코드 보기

 

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

// 전역변수

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int tc;
	cin >> tc;

	while(tc--) {
		int a, b;
		queue< pair<int, string> > q;
		int check[10000] = {false};

		// 초기화
		cin >> a >> b;
		q.push(make_pair(a, "")); check[a] = true;
		
		while(!q.empty()) {
			int i = q.front().first, next;
			string ans = q.front().second;
			q.pop();
			
			// 명령어 D
			next = (i * 2) % 10000;
			if(!check[next]) {
				if(next == b) { cout << ans + "D"; break; }
				q.push(make_pair(next, ans + "D"));
				check[next] = true;
			}
			// 명령어 S
			next = ((i == 0) ? 9999 : i - 1);
			if(!check[next]) {
				if(next == b) { cout << ans + "S"; break; }
				q.push(make_pair(next, ans + "S"));
				check[next] = true;
			}
			// 명령어 L
			next = (i / 1000) + (i % 1000) * 10;
			if(!check[next]) {
				if(next == b) { cout << ans + "L"; break; }
				q.push(make_pair(next, ans + "L"));
				check[next] = true;
			}
			// 명령어 R
			next = (i % 10) * 1000 + (i / 10);
			if(!check[next]) {
				if(next == b) { cout << ans + "R"; break; }
				q.push(make_pair(next, ans + "R"));
				check[next] = true;
			}
		}
		cout << "\n";
	}

	return 0;
}