2022.03.06 [백준] (python 파이썬) DSLR

 

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

9019번: DSLR

---

풀이

코드를 작성 할 때, D,S,L,R상황을 모두 생각해 주어야한다. 그래서 각 상황을 함수로 만들었다.

이 후 x가 y가 되기 위한 최소한의 움직임을 저장해야 하기 때문에 deq에 (바뀐 숫자, 수행한 연산)을 저장해 연산을 하게 되면 숫자와 연산을 업데이트해 deq에 저장해주었다.

from collections import deque
 
 
def D(a):
    return (a*2)%10000
 
def S(a):
    if a==0:
        return 9999
    else:
        return a-1
 
def L(a):
    return (a%1000)*10+a//1000
 
def R(a):
    return (a//10)+(a%10)*1000
 
def bfs(x,y):
    arr = [0] * 10001
    deq=deque()
    deq.append([x,''])
    while deq:
        a,b=deq.popleft()
        if a==y:
            return b
        if arr[D(a)]==0:
            deq.append([D(a),b+'D'])
            arr[D(a)]=a
        if arr[S(a)]==0:
            deq.append([S(a),b+'S'])
            arr[S(a)] = a
        if arr[L(a)] == 0:
            deq.append([L(a),b+'L'])
            arr[L(a)] =a
        if arr[R(a)] == 0:
            deq.append([R(a),b+'R'])
            arr[R(a)] =a
 
for _ in range(int(input())):
    x,y=map(int, input().split())
    print(bfs(x,y))