[파이썬] 백준 9019번 : DSLR

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

9019번: DSLR

 

 

from collections import deque

# def f_D(A):

#     return A*2 % 10000,'D'

# def f_S(A):

#     if A==0:

#         return 9999,'S'

#     else:

#         return A-1,'S'

# def f_L(A):

#     A = list(str(A))

#     temp = A[0]

#     del A[0]

#     A.append(temp)

#     A = ''.join(A)

#     return int(A),'L'

 

# def f_R(A):

#     A = list(str(A))

#     temp = A[-1]

#     del A[-1]

#     A.insert(0,temp)

#     A = ''.join(A)

#     return int(A),'R'

def f_D(k):

    return (2*k)%10000,'D'

def f_S(k):

    if k==0:

        return 9999,'S'

    else:

        return k-1,'S'

def f_L(k):

    return (k%1000)*10+(k//1000),'L'

def f_R(k):

    return (k//10)+(k%10)*1000,'R'

def solve_dp(A,B):

    q.append(A)

    while q:

        x = q.popleft()

        # print([f_D(x),f_S(x),f_L(x),f_R(x)])

        for i,j in [f_D(x),f_S(x),f_L(x),f_R(x)]:

            if pre_arr[i]==-1:

                pre_arr[i] = x

                q.append(i)

                temp_arr[i] = j

 

    k = ''    

    while B!=A:

       k += temp_arr[B]

       B = pre_arr[B]

 

    return k[::-1]

for _  in range(int(input())):

    A, B = map(int,input().split())

    q = deque()

    pre_arr = [-1]*(10**4)

    temp_arr = ['']*(10**4)

    print(solve_dp(A,B))

 

 

맨 처음 리스트로 함수를 만들었으나 너무 오래걸려서 다른 분 블로그를 참고하여

modular를 이용하여 함수를 만들었다.