[백준] 9019번 : DSLR

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

9019번: DSLR

해당 문제는 너비 우선 탐색으로 문제를 해결한다. 첫 숫자를 큐에 넣고 pop하여 4가지의 연산을 한뒤에 다시 큐에 넣는다.

큐와 팝을 반복을 하면서 B의 숫자가 만들어질때까지 결과값을 구한다. visited처리는 연산한 값으로 visited처리를 하였습니다.

해당 visited값 안에는 연산의 누적 합니다.

 

from collections import deque
T = int(input())
ops = ['D','S','L','R']

for _ in range(T):
    A, B = map(int, input().split())
    queue = deque()
    queue.append(A) # 값과 빈 배열을 넣는다.
    visited = [None for _ in range(10000)]
    visited[A] = ''
    while queue:
        register = queue.popleft()
        
        if register == B: # 만약 조건을 찾는다면
            print(visited[B])
            break
        
        for op in ops:
            if op == 'D': # D연산은 2배를 취한뒤, 9999보다 큰경우에는 10000으로 나눈 나머지 값으로 취한다.
                newregister = (register * 2) % 10000
            elif op == 'S': # -1을 한 결과를 레지스터리에 넣는다. 레지스터리가 0이라면 9999를 넣는다.
                newregister = (register - 1) % 10000
            elif op == 'L': # 왼편으로 회전시켜레지스터리에 저장한다.
                newregister = (register % 1000) * 10 + register // 1000
            elif op == 'R': # 오른편으로 레지스터를 저장한다.
                newregister = (register % 10) * 1000 + register // 10
            
            if visited[newregister] is None:
                visited[newregister] = visited[register] + op
                queue.append(newregister)