이번 문제는 BFS를 통해 해결하였다. 4개의 계산을 한번씩 적용하여 방문처리가 되어 있지 않은 수일 경우에 큐에 넣어 탐색을 적용하였다. 어려운문제가 아니었는데 시도를 조금 많이 한 것 같다 ..

Code

from collections import deque

def bfs():
    q = deque()
    q.append([a, ""])
    while q:
        cur, path = q.popleft()
        dn = (cur * 2) % 10000
        if dn == b:
            return path + "D"
        elif arr[dn] == 0:
            arr[dn] = 1
            q.append([dn, path + "D"])
        sn = (cur - 1)%10000
        if sn == b:
            return path + "S"
        elif arr[sn] == 0:
            arr[sn] = 1
            q.append([sn, path + "S"])
        ln = int(cur % 1000 * 10 + cur / 1000)
        if ln == b:
            return path + "L"
        elif arr[ln] == 0:
            arr[ln] = 1
            q.append([ln, path + "L"])
        rn = int(cur % 10 * 1000 + cur // 10)
        if rn == b:
            return path + "R"
        elif arr[rn] == 0:
            arr[rn] = 1
            q.append([rn, path + "R"])
t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    arr = [0 for _ in range(10000)]
    print(bfs())