BOJ 9019 DSLR(Python 3)

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

시간이 오래 걸리지 않는 문제였는데, 뒤집어서 출력해야 하는 것을 그대로 출력하는 것으로 계속 제출해서 연달아 틀렸습니다가 나온 문제다 

코드 내부에 문제가 있는 줄 알아서 확인해보니 내 눈엔 문제가 없어보여서 코드를 수차례나 지우고 다시 쓰고를 반복했따 ㅠㅡㅠ

DSLR은 숨바꼭질 4의 10% 업그레이드? 한 BFS 문제이다.

나는 문자열로 L,R을 구현하면 시간 초과가 나왔는데, 다른 분이 하신 코드를 보니 문자열을 이용해서 L,R을 구현해도 통과를 할 수 있다.

출력은 숨바꼭질 4와 똑같이 역추적하는 리스트 하나를 만들어서 while문을 돌려서 한 줄의 문자열을 만든다음, 뒤집어서 출력을 하면 된다.

그리고 Python3은 매우 느리니 Pypy3으로 제출해야만 한다.

코드 확인

from collections import deque
def D(k):
    return (2*k)%10000,'D'
def S(k):
    if k==0:
        return 9999,'S'
    else:
        return k-1,'S'
def L(k):
    return (k%1000)*10+(k//1000),'L'
def R(k):
    return (k//10)+(k%10)*1000,'R'
 
for __ in range(int(input())):
    n,m=map(int,input().split())
    A,F=['']*10000,[-1]*10000
    q=deque()
    q.append(n)
    F[n]=-2
    while q:
        x=q.popleft()
        for i,j in [D(x),S(x),L(x),R(x)]:
            if F[i]==-1:
                q.append(i)
                A[i]=j
                F[i]=x
    k=''
    while m!=n:
        k+=A[m]
        m=F[m]
    print(k[::-1])