백준 #9019 DSLR (파이썬)

문제 링크

내 수준에서는 어려운 문제(골드 4)인데,
아이디어가 금방 생각났고, 코드가 원트에 매우 깔끔하게 나왔고,
게다가 막힘없이 풀어서 통과까지 한 기념으로 뿌듯해서 코드를 올려본다.

전형적인 bfs를 이용한 연산 최소 횟수 찾기 문제다.
이 문제의 독특한 점은, 최소 횟수를 출력하는 게 아니라 연산 내용을 출력하는 것이다.
따라서 별도 tuple을 생성하여 연산 과정을 함께 누적해나가는 식으로 작성했다.

# bfs
# 가능한 연산 다 해보는 거죠 뭐
# 나올때까지? 예
# 이렇게 생각하니까 완전 어려운 것도 아니네
# bfs 최소니까 deque 필요 없지

import sys

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

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

def L(n):
    d1 = n // 1000
    n %= 1000
    d2 = n // 100
    n %= 100
    d3 = n // 10
    n %= 10
    d4 = n
    return d2*1000 + d3*100 + d4*10 + d1

def R(n):
    d1 = n // 1000
    n %= 1000
    d2 = n // 100
    n %= 100
    d3 = n // 10
    n %= 10
    d4 = n
    return d4*1000 + d1*100 + d2*10 + d3

OP = ['D', 'S', 'L', 'R']

def bfs(A, B):
    visited = [False] * 10000
    q = [(A, (''))]
    visited[A] = True
    while q:
        q_copy = q[:]
        q = []
        for e, path in q_copy:
            results = [D(e), S(e), L(e), R(e)]
            for idx, result in enumerate(results):
                if not visited[result]:
                    if result == B:
                        return path+OP[idx]
                    visited[result] = True
                    q.append((result, path+OP[idx]))

if __name__ == '__main__':    
    T = int(sys.stdin.readline().rstrip())
    for _ in range(T):
        A, B = map(int, sys.stdin.readline().rstrip().split())
        print(bfs(A, B))