백준 알고리즘 9019번 DSLR(python)

생각보다 쉬운 BFS 문제이다. 변환된 숫자와 여태까지 사용한 명령어를 큐에 같이 append, pop 해주면 된다.

변환된 숫자와 B가 같다면 여태까지 사용한 명령어(res)를 리턴하면 끝이다.

from collections import deque

def bfs(A, B):
    q = deque()
    q.append((A, ""))
    while q:
        n, res = q.popleft()
        D = n*2 % 10000
        if D == B: return res+'D'
        elif check[D] == 0:
            check[D] = 1
            q.append((D, res+'D'))
        S = n-1 if n > 0 else 9999
        if S == B: return res+'S'
        elif check[S] == 0:
            check[S] = 1
            q.append((S, res+'S'))
        L = (n%1000)*10 + n//1000
        if L == B: return res+'L'
        elif check[L] == 0:
            check[L] = 1
            q.append((L, res+'L'))
        R = (n%10)*1000 + n//10
        if R == B: return res+'R'
        elif check[R] == 0:
            check[R] = 1
            q.append((R, res+'R'))

for _ in range(int(input())):
    A, B = map(int, input().split())
    check = [0]*10000
    print(bfs(A, B))