백준 9019 DSLR - C++

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

문제 설명

입력값 A,B가 주어지면 A를 D,S,L,R 연산을 최소한으로 사용하여 입력값 B를 만드는 문제이다.
주어진 D,S,L,R 연산은 이렇다
D는 A의 값을 2배로 만들기
S는 A의 값을 -1 해주기
L은 A의 자릿수들을 왼쪽으로 회전시키기
R은 A의 자릿수들을 오른쪽으로 회전시키는것이다.
처음 이 문제를 풀었을당시, L, R 연산할때 문자열을 이용하여 자릿수를 이동하는식으로 했더니 시간초과가 나왔다 이유를 찾아보니 string에 어떤 문자를 더하는 것은, 기존의 문자열을 전부 새로운 메모리 공간에 복사하고 그 뒤에 문자를 덧붙여서 새로운 string을 만들어내는 것이기 때문에 시간을 많이 쓴다고 한다.
그래서 다른 방법으로 나머지 연산을 이용하여 L,R 연산을 구현하였다.

소스코드

#include <iostream>
#include <queue>
#include <string>
#include <cmath>
#include <memory.h>

using namespace std;

int n, m;
bool visited[10001];

void bfs()
{
    string now_st;
    queue<pair<int, string> >q;
    q.push(make_pair(n,now_st));
    while (!q.empty())
    {
        int now = q.front().first;
        now_st = q.front().second;
        q.pop();
        if (now == m)
        {
            cout << now_st << "\n";
            return ;
        }
        int ovo;
        // D
        if (now * 2 > 9999)
            ovo = (now * 2) % 10000;
        else
            ovo = now * 2;
        if (!visited[ovo])
        {
           visited[ovo] = true;
           q.push(make_pair(ovo,now_st + 'D'));
        }
        // S
        if (now == 0)
            ovo = 9999;
        else
            ovo = now - 1;
        if (!visited[ovo])
        {
            visited[ovo] = true;
            q.push(make_pair(ovo,now_st + 'S'));
        }
        // L
        ovo = (now % 1000) * 10 + now / 1000;
        if (!visited[ovo])
        {
            visited[ovo] = true;
            q.push(make_pair(ovo,now_st + 'L'));
        }
        // R
        ovo = (now % 10) * 1000 + (now / 10);
        if (!visited[ovo])
        {
            visited[ovo] = true;
            q.push(make_pair(ovo, now_st+'R'));
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int a;
    cin >> a;
    
    for (int i = 0; i < a; i++)
    {
        cin >> n >> m;
        bfs();
        memset(visited,false,10000);
    }
    return 0;
}