BOJ - 9019 - DSLR

import sys
from collections import deque

def BFS(A, B):
    arr = [0 for _ in range(10001)]

    Q = deque()
    Q.append((A, ""))

    while Q:
        number, move = Q.popleft()

        next = (number * 2) % 10000
        if next == B:
            return move + "D"
        elif arr[next] == 0:
            arr[next] = 1
            Q.append((next, move + "D"))

        next = number -1 if number != 0 else 9999
        if next == B:
            return move + "S"
        elif arr[next] == 0:
            arr[next] = 1
            Q.append((next, move + "S"))

        next = (number % 1000 * 10 + number // 1000)
        if next == B:
            return move + "L"
        elif arr[next] == 0:
            arr[next] = 1
            Q.append((next, move + "L"))

        next = (number % 10 * 1000 + number // 10)
        if next == B:
            return move + "R"
        elif arr[next] == 0:
            arr[next] = 1
            Q.append((next, move + "R"))

def solution():
    T = int(input())
    for _ in range(T):
        A, B = map(int, sys.stdin.readline().split())
        print(BFS(A, B))
solution()

https://www.acmicpc.net/problem/9019