[BFS / 파이썬] 백준 9019번 : DSLR / 골드 4

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

9019번: DSLR

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에

www.acmicpc.net

import collections

def op_d(n):
    return (2*n) % 10000

def op_s(n):
    if n == 0:
        return 9999
    else:
        return n-1

def op_l(n):
    d1, d2, d3, d4 = n_to_digit(n)
    return digit_to_n(d2, d3, d4, d1)

def op_r(n):
    d1, d2, d3, d4 = n_to_digit(n)
    return digit_to_n(d4, d1, d2, d3)

def n_to_digit(n):
    d1 = n // 1000
    n -= d1*1000
    d2 = n // 100
    n -= d2*100
    d3 = n // 10
    n -= d3*10
    d4 = n
    return d1, d2, d3, d4

def digit_to_n(d1, d2, d3, d4):
    return d1*1000 + d2*100 + d3*10 + d4


t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    dct = collections.defaultdict(int)

    q = collections.deque()
    q.append((a, ''))
    find = False

    while q:
        for _ in range(len(q)):
            cur, command = q.popleft()
            if cur == b:
                print(command)
                find = True
                break

            na1 = op_d(cur)
            if dct[na1] == 0:
                dct[na1] = 1
                q.append((na1, command + 'D'))

            na2 = op_s(cur)
            if dct[na2] == 0:
                dct[na2] = 1
                q.append((na2, command + 'S'))

            na3 = op_l(cur)
            if dct[na3] == 0:
                dct[na3] = 1
                q.append((na3, command + 'L'))

            na4 = op_r(cur)
            if dct[na4] == 0:
                dct[na4] = 1
                q.append((na4, command + 'R'))

        if find:
            break

전형적인 bfs 문제