9019: DSLR

• 간단한 bfs 문제인데 시간 복잡도를 조금 신경써줘야하는 문제였다
• 1) visit 리스트를 통해 이미 방문한 노드를 중복 방문하지 않도록 처리해줌
• 2) L연산과 R연산을 처음에는 string으로 변환하고 padding 해주는 방식으로 접근했는데, 그렇게 하면 연산 시간이 오래 걸려서 수식으로 한줄로 표현해주는 방식으로 수정함
• 3) bfs, dfs에서 노드는 독립적으로 존재하기 때문에, queue에 넣어주는 node를 [nextA, trace + 'D or S or L or R'] 형식의 list로 표현해주어 trace를 기록해줌 (trace는 문자열)

import sys
from collections import deque

def calD(A):
    return (A * 2) % 10000

def calS(A):
    return (A - 1) % 10000

def calL(A):
    return A // 1000 + (A % 1000) * 10

def calR(A):
    return A // 10 + (A % 10) * 1000


def bfs(A, B):
    queue = deque([])
    queue.append([A, ''])
    visit[A] = True

    while queue:
        currA, trace = queue.popleft()

        if currA == B:
            print(trace)
            break

        nextA = calD(currA)
        if not visit[nextA]:
            visit[nextA] = True
            queue.append([nextA, trace + 'D'])

        nextA = calS(currA)
        if not visit[nextA]:
            visit[nextA] = True
            queue.append([nextA, trace + 'S'])

        nextA = calL(currA)
        if not visit[nextA]:
            visit[nextA] = True
            queue.append([nextA, trace + 'L'])
            
        nextA = calR(currA)
        if not visit[nextA]:
            visit[nextA] = True
            queue.append([nextA, trace + 'R'])

T = int(input())
for _ in range(T):
    A, B = map(int, sys.stdin.readline()[:-1].split())
    visit = [False for i in range(10001)]
    bfs(A, B)