너비 우선 탐색으로 모든 노드를 방문하다가 b를 찾았다면, 종료하면 된다.
(1) D : n은 2배로 나눈다. (10,000보다 큰 경우, 10000으로 나눈 나머지) →
현재숫자 * 2 % 10000
(2) S : n에서 1을 뺀다. (0인 경우, 9999로) →(현재숫자-1) % 10000
(3) L : n의 각 자릿수를 왼편으로 회전 (d1d2d3d4 -> d2d3d4d1) →((현재 숫자 // 1000) + (현재 숫자 % 1000) * 10) % 10000
(4) R : n의 각 자릿수를 오른편으로 회전 →((현재숫자 % 10) * 1000 + (현재숫자 // 10) % 10000)
import sys
from collections import deque
read = sys.stdin.readline
t = int(read())
def bfs():
q = deque()
q.append((a, ''))
visited = [False] * 10000
while q:
next_data, path = q.popleft()
if next_data == b:
print(path)
break
num = (next_data * 2) % 10000
if not visited[num]:
visited[num] = True
q.append((num, path + 'D'))
num = (next_data - 1) % 10000
if not visited[num]:
visited[num] = True
q.append((num, path + 'S'))
num = (next_data // 1000 + (next_data % 1000) * 10) % 10000
if not visited[num]:
visited[num] = True
q.append((num, path + 'L'))
num = ((next_data % 10) * 1000 + next_data // 10) % 10000
if not visited[num]:
visited[num] = True
q.append((num, path + 'R'))
while t > 0:
a, b = map(int, read().split())
bfs()
t -= 1
채점 결과