BOJ 9019 DSLR

이 문제는 A라는 수를  DSLR 규칙을 이용하여 B로 바꾸는데 필요한 최소한의 명령어를 나열하여 출력하는 문제이다.

처음 문제를 보았을때 숫자를 자릿수로 쪼개서 deque으로 저장할까 라는 생각을 하였다. 이 방법을 이용하면 L,R은 쉽게 풀수 있지만 D,S는 자릿수를 다시 계산해야 하는 번거로움이 생긴다. 그냥 숫자로 접근해보자!!

 

DSLR을 숫자로 접근해보면 다음과 같은 식으로 표현할 수 있다.

D: (n * 2) % 10000

S: (n - 1) < 0?9999:n - 1

L: (n % 1000) * 10 + (n / 1000)

R: (n % 10) * 1000 + (n / 10)

 

 이제 A숫자에서 B로 만들기 위해 우리는 DSLR을 반복해서 수행해야 한다. 처음에는 시뮬레이션 문제인가 헷갈렸다. 알고리즘 힌트를 보고 너비우선 탐색인것을 알고 다시 생각해보니 충분히 그럴수 밖에 없다고 생각이 들었다. 기존의 BFS 문제는 전형적으로 가로세로 좌표에서 상하좌우 또는 상하좌우, 대각선으로 탐색을 뻗어 나간다. 그런 유형의 문제를 많이 풀다보니 나도 모르게 BFS는 상하좌우 라고 생각이 들었던것 같다. 

 

BFS 방식으로 문제를 풀때 핵심은 visited를 표시하여 중복을 제거해주는 것이다. 

예를들어 1234 을 LLLLL 움직이는 것은 L 한번 움직이는 것과 동일하다. 따라서 DSLR을 움직일때마다 변하는 숫자를 visited 처리해주어 큐에 들어가는 중복을 제거해 주어야 한다.

 

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

int visited[10001];

string solution()
{
	int  a, b;
	cin >> a >> b;

	queue<pair<int, string>> q;
	q.push({ a,"" });
	visited[a] = true;

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

		if(num == b)
		{
			cout << s << "\n";
			break;
		}

		int nextD = num, nextS = num, nextL = num, nextR = num;
		
		nextD = (num * 2) % 10000;
		if(!visited[nextD] || num != 0)
		{
			visited[nextD] = true;
			if(nextD == b)
			{
				return s + "D";
			}
			q.push({nextD,s + "D" });
		}
		

		nextS = (num - 1) < 0?9999:num - 1;
		if(!visited[nextS])
		{
			visited[nextS] = true;
			if(nextS == b)
			{
				return s + "S";
			}
			q.push({ nextS,s + "S" });
		}
		

		nextL = (num % 1000) * 10 + (num / 1000);
		if(!visited[nextL])
		{
			visited[nextL] = true;
			if(nextL == b)
			{
				return s + "L";
			}
			q.push({ nextL,s + "L" });
		}
		

		nextR = (num % 10) * 1000 + (num / 10);
		if(!visited[nextR])
		{
			visited[nextR] = true;
			if(nextR == b)
			{
				return s + "R";
			}
			q.push({ nextR,s + "R" });
		}
	}
}

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

	int t;
	cin >> t;

	for(int i = 0; i < t; i++)
	{
		memset(visited, false, sizeof(visited));
		cout<< solution()<<"\n";
	}
}