[백준 9019 골드4] DSLR (BFS/Python) -/3

아래 코드는 시간초과 나는 코드다.
원인을 아직 모르겠다.
정답은 잘 맞게 돌아가는데 시간초과가 나는군.

import sys
from collections import defaultdict, deque

def make_4dgit_str(num):
    num = str(num)
    while(len(num) < 4):
        num = '0'+num
    return num

def D(num):
    num = 2*num%10000
    return num

def S(num):
    if num ==0:
        num = 9999
    else:
        num -= 1
    return num

def L(num):
    num = make_4dgit_str(num)
    num = int(num[1]+num[2]+num[3]+num[0])
    return num


def R(num):
    num = make_4dgit_str(num)
    num = int(num[3]+num[0]+num[1]+num[2])
    return num
    

def bfs(num):
    visited = defaultdict(str) # {"3412": [LL]}
    q.append(num)
    visited[num] = "0"
    while q:
        now = q.popleft()
        tmp_dict = {"S": S(now), "D": D(now), "R": R(now), "L": L(now)}
        for key, value in tmp_dict.items():
            if not value in visited:
                visited[value] = visited[now]+key
                q.append(value)
            if value == end:
                print(visited[value][1:])
                return visited[value][1:]
    

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        start, end = map(int, sys.stdin.readline().split())
        q = deque()
        bfs(start)