백준 9019 DSLR (파이썬)

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

9019번: DSLR

1. 주어진 조건에 맞게 이동할 수 있도록 bfs 안의 조건문을 설계

2. 주어진 입력으로부터 조건에 맞게 bfs로 경로를 저장하며 이동

3. 목표값에 도달하면 저장된 경로를 출력 

from collections import deque
import sys

input = sys.stdin.readline

def bfs(x):
    q.append([x, ""])
    c[x] = 1
    while q:
        x, d = q.popleft()
        if x == y:
            return d
        if 2*x <= 9999 and c[2*x] == 0:
            c[2*x] = 1
            q.append([2*x, d+'D'])
        if 2*x > 9999 and c[(2*x) % 10000] == 0:
            c[(2*x) % 10000] = 1
            q.append([(2*x) % 10000, d+'D'])
        if x-1 >= 0 and c[x-1] == 0:
            c[x-1] = 1
            q.append([x-1, d+'S'])
        if x-1 < 0 and c[9999] == 0:
            c[9999] = 1
            q.append([9999, d+'S'])
        nx = int((x % 1000) * 10 + x / 1000)
        if c[nx] == 0:
            c[nx] = 1
            q.append([nx, d+'L'])
        nx = int((x % 10) * 1000 + x / 10)
        if c[nx] == 0:
            c[nx] = 1
            q.append([nx, d+'R'])

tc = int(input())
while tc:
    c = [0 for _ in range(10000)]
    q = deque()
    x, y = map(int, input().split())
    ans = bfs(x)
    print(ans)
    tc -= 1