문제풀이/DFS & BFS
[PyPy] [BFS] 백준 9019 DSLR
승무_
2022. 5. 26. 21:03
문제
https://www.acmicpc.net/problem/9019
9019번: DSLR
네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에
www.acmicpc.net
코드
import sys
from collections import deque
input = sys.stdin.readline
t = int(input())
def bfs(a, b):
queue = deque()
queue.append([a, ''])
while queue:
c, d = queue.popleft()
temp = (c * 2) % 10000
if temp == b:
return d + 'D'
elif dp[temp] == 0:
dp[temp] = 1
queue.append([temp, d + 'D'])
temp = c - 1 if c != 0 else 9999
if temp == b:
return d + 'S'
elif dp[temp] == 0:
dp[temp] = 1
queue.append([temp, d + 'S'])
temp = c // 1000 + c % 1000 * 10
if temp == b:
return d + 'L'
elif dp[temp] == 0:
dp[temp] = 1
queue.append([c // 1000 + c % 1000 * 10, d + 'L'])
temp = c % 10 * 1000 + c // 10
if temp == b:
return d + 'R'
elif dp[temp] == 0:
dp[temp] = 1
queue.append([c % 10 * 1000 + c // 10, d + 'R'])
for _ in range(t):
a, b = map(int, input().split())
dp = [0] * 10001
print(bfs(a, b))