[백준]Baekjoon9019(BFS,큐)

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

풀이

전형적으로 BFS를 사용하는 문제이다.

처음에 이 문제를 풀 때 'L'연산과 'R'연산을 하는 과정에서 비효율적으로 코드를 짜서

문제해결에 성공하지 못했는데 

'L'연산의 경우 int tmp = (x % 1000) * 10 + x / 1000; 

'R'연산의 경우 int tmp = (x / 10) + (x % 10) * 1000;

이렇게 식 하나로 정리했더니 문제를 해결할 수 있었다.

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

bool visit[10000];

char cmd[] = { 'D','S','L','R' };
int main()
{
	int testcase;
	scanf("%d", &testcase);

	while (testcase--)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		queue<pair<int, string>> q;
		q.push(make_pair(a, ""));
		memset(visit, 0, 10000);
		visit[a] = true;
		while (!q.empty())
		{
			int x = q.front().first;
			string y = q.front().second;
			q.pop();
			if (x == b) {
				cout << y << '\n'; break;
			}
			for (int i = 0; i < 4; i++) {
				if (cmd[i] == 'D') {
					int tmp = (x * 2) % 10000;
					if (!visit[tmp]) {
						q.push(make_pair(tmp, y + 'D'));
						visit[tmp] = true;
					}
				}
				else if (cmd[i] == 'S') {
					int tmp = x - 1;
					if (tmp == -1) tmp = 9999;
					if (!visit[tmp]) {
						q.push(make_pair(tmp, y + 'S'));
						visit[tmp] = true;
					}
				}
				else if (cmd[i] == 'L') {
					int tmp = (x % 1000) * 10 + x / 1000;
					if (!visit[tmp]) {
						q.push(make_pair(tmp, y + 'L'));
						visit[tmp] = true;
					}
				}
				else if (cmd[i] == 'R') {
					int tmp = (x / 10) + (x % 10) * 1000;
					if (!visit[tmp]) {
						q.push(make_pair(tmp, y + 'R'));
						visit[tmp] = true;
					}
				}
			}
		}
	}
}