[백준/BOJ] 9019번 DSLR (C++)

www.acmicpc.net/problem/9019

9019번: DSLR

BFS 문제입니다. (다시 풀기)

D연산과 S연산은 어렵지 않고, L연산과 R연산만 잘 처리해주면 되는데, 처음에는 현재 숫자를 문자열로 바꾸어 L연산인 경우는 맨 앞의 문자를 뒤로 보내고, R연산인 경우는 맨 뒤의 문자를 앞으로 보내게끔 구현하려 했으나 코드가 좀 복잡해질 것 같아서 mod 연산을 이용하여 구현해봤습니다. 예를들어 입력값이 1234라고 가정해봅시다. L연산과 R연산을 했을 때 결과는 다음과 같습니다.

 

L : 1234 -> 2341

R : 1234 -> 4123

 

L연산은 먼저 1234을 1000으로 나눈 나머지 값에 곱하기 10을 하고, 1234를 1000으로 나눈 몫을 더해주면 됩니다.

R연산은 1234를 10으로 나눈 나머지 값에 곱하기 1000을 하고, 1234를 10으로 나눈 몫을 더해주면 됩니다.

(수가 두자리, 세자리라도 직접 해보시면 문제 없다는 것을 확인할 수 있습니다.)

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

bool visit[100001];

void BFS(int start, int target) {
	memset(visit, false, sizeof(visit));
	queue<pair<int, string> > q; // 현재 숫자, 연산 목록  
	q.push({start, ""});
	visit[start] = true;
	while(!q.empty()) {
		int now = q.front().first;
		string op = q.front().second;
		q.pop();
		
		// 종료 조건  
		if(now == target) {
			cout<<op<<"\n";
			break;
		}
		
		// D 연산 
		int next = now * 2;
		next = next > 9999 ? next % 10000 : next;
		if(!visit[next]) {
			q.push({next, op + "D"});
			visit[next] = true;
		}
		
		// S 연산
		next = now == 0 ? 9999 : now - 1;
		if(!visit[next]) {
			q.push({next, op + "S"});
			visit[next] = true;
		}
		
		// L 연산
		next = (now % 1000) * 10 + now / 1000;
		if(!visit[next]) {
			q.push({next, op + "L"});
			visit[next] = true;
		}
		
		// R 연산 
		next = (now / 10) + (now % 10) * 1000;
		if(!visit[next]) {
			q.push({next, op + "R"});
			visit[next] = true;
		}
	}
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin>>T;
    while(T--) {
    	int start, target;
    	cin>>start>>target;
    	BFS(start, target);
	}
}