📌 Problem.

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

주어진 계산기는 4자리 레지스터 하나를 가지고 값을 저장한다.
주어진 연산 D, S, L, R을 적당히 사용해
정수 A를 B로 바꾸는 최단 연산 조합를 찾는 문제이다.

📌 Solution.

레지스터가 네 자리라는 점에 주목해야 한다.
가령 (0)123에 L를 적용했을 때,(0)312가 아닌 1230이 된다.

그렇다고 레지스터를 길이가 4인 리스트로 표현함으로써 슬라이싱으로 레지스터를 조작했다가는 시간 초과를 마주할 것이다.
수학 연산을 통해 정수를 직접 조작하는 것이 훨씬 쉽고 효율적이다.

BFS인 만큼 방문 체크를 해주지 않으면 메모리 초과가 발생할 수 있다.

import sys
import collections

input = sys.stdin.readline

for _ in range(int(input())):
    A, B = map(int, input().split())
    queue = collections.deque([(A, '')])
    visit = [0] * 10000
    visit[A] = 1

    def push(number, operation):
        if not visit[number]:
            visit[number] = 1
            queue.append((number, operation))

    while queue:
        n, op = queue.popleft()  # (number, operation)
        if n == num2:
            print(op)
            break
        push((n * 2) % 10000, op + 'D')
        push((n - 1) % 10000, op + 'S')
        push((n % 1000) * 10 + n // 1000, op + 'L')
        push((n % 10) * 1000 + n // 10, op + 'R')

정수를 조작할 때, '수학 연산으로 처리할 수 있지 않을까?'라는 생각을 한 번쯤은 반드시 해보아야겠다는 통찰을 준 문제이다.