[Python]동적계획법과 최단거리 역추적 백준 9019

 문제

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

문제는 복잡해보이지만 읽어보면 굉장히 단순하다는것을 알수있다.

큐를 이용하여 각 단계마다 D,S,L,R에 해당하는 연산의 결과를 넣어주고 B가 나올때 까

지 돌리면된다.큐에 넣을때 이전연산값에 각단계의 연산값을 추가하여 넣어주었으며 

중복계산을 방지하기위해 0~9999까지의 연산을 한번이라도 했으면 배열로 체크를 하여

 다시 연산하지 않도록해주었다. 이전단계에서 어떤연산을 통해 왔는지만 저장하게 된다

면 D연산이나 여러가지경우에서 문제가 생길거같다.

 파이썬으로는 통과 하지 못하였고 pypy3를 통해 통과하였다.

import sys
from collections import deque
 
for _ in range(int(sys.stdin.readline())):
    check=[True for _ in range(10000)]
    A,B=map(int,sys.stdin.readline().split())
    q=deque()
    q.append([A,""])
    while q:
        C=q.popleft()
        if C[0]==B:
            print(C[1])
            break
 
        #D
        D=C[0]*2%10000
        if check[D]==True:#아직 한번도 만들어진적이 없다면
            check[D]=False
            q.append([D,C[1]+"D"])
        #S
        if C[0]==0:
            S=9999
        else:
            S=C[0]-1
        if check[S]==True:
            check[S]=False
            q.append([S,C[1]+"S"])
 
        #L
        L=(C[0]%1000)*10+C[0]//1000
        if check[L]==True:
            check[L]=False
            q.append([L,C[1]+"L"])
 
        #R
        R=(C[0]%10)*1000+C[0]//10
        if check[R]==True:
            check[R]=False
            q.append([R,C[1]+"R"])