[C/C++] 백준 9019번 - DSLR

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
using namespace std;

int T,A,B;
bool visit[10000];


int D(int x)
{
	x *= 2;
	if (x > 9999) x %= 10000;
	return x;
}

int S(int x)
{
	if (x == 0) x = 9999;
	else x--;
	return x;
}

int L(int x)
{
	int y = x / 1000;
	x %= 1000;
	x = x * 10 + y;
	return x;
}

int R(int x)
{
	int y = x % 10;
	x = 1000*y + (x - y) / 10;
	return x;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> T;

	while (T--)
	{
		cin >> A >> B;
		string ans = "";
		for (int i = 0; i < 10000; i++)
			visit[i] = false;

		queue<pair<int, string>> q; // <정수, 명령어>
		q.push({ A,ans });

		while (true)
		{
			int now_num = q.front().first;
			string now_str = q.front().second;
			q.pop();

			if (now_num == B)
			{
				ans = now_str;
				break;
			}

			int next_num = 0;

			next_num = D(now_num);
			if (!visit[next_num])
			{
				q.push({ next_num, now_str + 'D' });
				visit[next_num] = true;
			}
			//cout << "D : " << next_num << '\n';

			next_num = S(now_num);
			if (!visit[next_num])
			{
				q.push({ next_num, now_str + 'S' });
				visit[next_num] = true;
			}
			//cout << "S : " << next_num << '\n';

			next_num = L(now_num);
			if (!visit[next_num])
			{
				q.push({ next_num, now_str + 'L' });
				visit[next_num] = true;
			}
			//cout << "L : " << next_num << '\n';

			next_num = R(now_num);
			if (!visit[next_num])
			{
				q.push({ next_num, now_str + 'R' });
				visit[next_num] = true;
			}
			//cout << "R : " << next_num << '\n';
		}
		cout << ans << '\n';
	}
}

 

풀이 방법

 

string 생성하고 복사하는 과정에서 시간초과가 발생하니 string 사용을 최소한으로 줄이면 코드 통과가 가능합니다.

 

그리고 "123"의 경우 L, R 명령으로 "231", "312"가 아닌

L -> "1230"

R -> "3012"

으로 변환되는것에 주의합시다.

 

www.acmicpc.net/problem/9019

9019번: DSLR