https://www.acmicpc.net/problem/9019
시간 6초, 메모리 256MB
input :
output :
조건 :
최소한의 명령어 나을 출력하는데, 가능한 명령어 나열이 여러가지일 수도 있다고 한다. 이는 BFS를 나타내는 것이라고 보고 BFS를 이용했다.
처음에는 D, S 를 10000과 0으로 조건을 나눠서 풀었는데 이 경우에 valueerror가 발생했다. 다른 분들의 풀이를 보니 10000 으로 나머지를 구해서 푸시길래 나도 이와 동일하게 바꾸었다.
LR의 경우에는 숫자가 1일 때, 0001 / 0010 으로 만들어 주어야 한다. 이는 str의 zfill 을 이용해서 4자리 중 숫자보다 앞 칸이 비어 있다면 0으로 채우게 만든다.
import sys
from _collections import deque
t = int(sys.stdin.readline())
for i in range(t):
a, b = map(int, sys.stdin.readline().split())
dp = [-1] * 10001
if len(str(a)) < 4:
a = str(a).zfill(4)
q = deque([(a, '')])
dp[int(a)] = 1
while q:
now_str, command = q.popleft()
if type(now_str) != str:
now_str = str(now_str)
now = int(now_str)
if now == b:
print(command)
break
next_num = (now * 2) % 10000
next_str = str(next_num)
if dp[next_num] == -1:
if next_num < 1000:
next_str = next_str.zfill(4)
dp[next_num] = 1
q.append((next_str, command + 'D'))
next_num = (now - 1) % 10000
next_str = str(next_num)
if dp[next_num] == -1:
if next_num < 1000:
next_str = next_str.zfill(4)
dp[next_num] = 1
q.append((next_str, command + 'S'))
next_str = now_str[1:] + now_str[0]
next_num = int(next_str)
if dp[next_num] == -1:
dp[next_num] = 1
q.append((next_str, command + 'L'))
next_str = now_str[3] + now_str[:3]
next_num = int(next_str)
if dp[next_num] == -1:
dp[next_num] = 1
q.append((next_str, command + 'R'))