1. 요약
DSLR 명령어를 이용하여 숫자 A를 숫자 B로 변환할 때, 나올 수 있는 최소 경로를 출력하는 문제.
이때 DSLR의 의미는 다음과 같다. 입력값으로 n이 주어질 때,
D: n을 (2*n) % 10000 변환
S: n이 0이면 n을 9999로 변환, n > 0 이면 n-1로 변환
L: n의 4자리수를 d1, d2, d3, d4라고 할 때, d2, d3, d4, d1으로 변환
R: n의 4자리를 d1, d2, d3, d4라고 할 때, d4, d1, d2, d3으로 변환
주의할 점은 L 또는 R명령어를 사용할 경우, n을 항상 4자리수로 두고 명령을 수행해야한다. 예를 들어 n이 5이고 L 명령어를 수행 한다고 해보자. n을 4자리수로 만들면 0005이고 여기서 L을 실행하면 결과는 0050이 되므로 50이된다.
이번엔 R 명령어를 실행해보자 n이 5일 때, R 명령어를 수행하면 n은 5000으로 변환된다.
2. 아이디어
L,R을 잘 이해하고 구현하는 것이 중요하다.
L의 경우 백이하 자리수의 숫자들이 왼쪽으로 가고 천 자리 숫자가 일의 자리로 가는 사실 이용해 구현한다.
R의 경우 일의 자리 숫자가 천의 자리로 이동하고, 천, 백, 십 자리의 숫자들이 오른쪽으로 가는 사실을 이용해 구현한다.
D,S,L,R을 구현한 후,BFS를 이용하여 해결한다.
3. 코드
import sys
from collections import deque
cmd = {0:'D', 1:'S', 2:'L', 3:'R'}
def D(n):
return (n * 2) % 10000
def S(n):
if n == 0: return 9999
return n - 1
def L(n):
return (n % 1000) * 10 + n // 1000
def R(n):
return (n % 10) * 1000 + n // 10
def solve():
a, b = map(int, sys.stdin.readline().rstrip().split())
visited = [False for _ in range(10000)]
q = deque()
q.append([a, ''])
visited[a] = True
while q:
cn, path = q.popleft()
if cn == b:
print(path)
break
nns = [D(cn), S(cn), L(cn), R(cn)]
for i in range(4):
nn = nns[i]
if not visited[nn]:
visited[nn] = True
q.append([nn, path+cmd[i]])
tc = int(sys.stdin.readline().rstrip())
while tc:
solve()
tc -= 1
