9019_DSLR

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

9019번: DSLR

 

 

bfs를 활용하면 되는 문제이다.

 

결국 이전 숨바꼭질 문제들과 비슷하게 풀 수 있다.

 

D,S,L,R 연산을 한번씩 한 후에 dp에 넣어주면서 풀면 된다.

 

만약 어떠한 연산으로 200이란 수가 나왔다면 그 다음에 200이 나온 경우에는 queue에 추가하지 않는 방식으로 문제를 풀면 될 것이다.

 

이때 역추적또한 해야하는데, 이전의 데이터를 굳이 넣진 않고 큐 구조에 답을 저장하는 공간을 따로 만들었다.

 

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())

def bfs(a,b):
    q = deque([(a,'')])
    while q:
        num,result = q.popleft()

        if num == b:
            print(result)
            return

        D = (2*num)%10000
        if not dp[D]:
            q.append((D,result+'D'))
            dp[D] = True
        S = (num-1)%10000
        if not dp[S]:
            q.append((S,result+'S'))
            dp[S] = True
        L = (10 * num + (num // 1000)) % 10000
        if not dp[L]:
            q.append((L, result + "L"))
            dp[L] = True

        # 4
        R = (num // 10 + (num % 10) * 1000) % 10000
        if not dp[R]:
            q.append((R, result + "R"))
            dp[R] = True

for _ in range(T):
    a,b = map(int,input().split())
    dp = [False] * 10000
    bfs(a,b)