백준
백준 9019 DSLR (파이썬)
chldkato
2020. 2. 17. 01:25
https://www.acmicpc.net/problem/9019
9019번: DSLR
문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경
www.acmicpc.net
1. 주어진 조건에 맞게 이동할 수 있도록 bfs 안의 조건문을 설계
2. 주어진 입력으로부터 조건에 맞게 bfs로 경로를 저장하며 이동
3. 목표값에 도달하면 저장된 경로를 출력
from collections import deque
import sys
input = sys.stdin.readline
def bfs(x):
q.append([x, ""])
c[x] = 1
while q:
x, d = q.popleft()
if x == y:
return d
if 2*x <= 9999 and c[2*x] == 0:
c[2*x] = 1
q.append([2*x, d+'D'])
if 2*x > 9999 and c[(2*x) % 10000] == 0:
c[(2*x) % 10000] = 1
q.append([(2*x) % 10000, d+'D'])
if x-1 >= 0 and c[x-1] == 0:
c[x-1] = 1
q.append([x-1, d+'S'])
if x-1 < 0 and c[9999] == 0:
c[9999] = 1
q.append([9999, d+'S'])
nx = int((x % 1000) * 10 + x / 1000)
if c[nx] == 0:
c[nx] = 1
q.append([nx, d+'L'])
nx = int((x % 10) * 1000 + x / 10)
if c[nx] == 0:
c[nx] = 1
q.append([nx, d+'R'])
tc = int(input())
while tc:
c = [0 for _ in range(10000)]
q = deque()
x, y = map(int, input().split())
ans = bfs(x)
print(ans)
tc -= 1