[PyPy] [BFS] 백준 9019 DSLR

문제

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

9019번: DSLR

코드

import sys
from collections import deque

input = sys.stdin.readline

t = int(input())

def bfs(a, b):
    queue = deque()
    queue.append([a, ''])

    while queue:
        c, d = queue.popleft()
        temp = (c * 2) % 10000
        if temp == b:
            return d + 'D'
        elif dp[temp] == 0:
            dp[temp] = 1
            queue.append([temp, d + 'D'])

        temp = c - 1 if c != 0 else 9999
        if temp == b:
            return d + 'S'
        elif dp[temp] == 0:
            dp[temp] = 1
            queue.append([temp, d + 'S'])

        temp = c // 1000 + c % 1000 * 10
        if temp == b:
            return d + 'L'
        elif dp[temp] == 0:
            dp[temp] = 1
            queue.append([c // 1000 + c % 1000 * 10, d + 'L'])

        temp = c % 10 * 1000 + c // 10
        if temp == b:
            return d + 'R'
        elif dp[temp] == 0:
            dp[temp] = 1
            queue.append([c % 10 * 1000 + c // 10, d + 'R'])

for _ in range(t):
    a, b = map(int, input().split())
    dp = [0] * 10001
    print(bfs(a, b))