DSLR

백준 9019

• 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
3. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
4. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

• 여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다.
• n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.
• 프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

입출력

입력	출력
3 1234 3412 1000 1 1 16	LL L DDDD

---

접근 방식

: bfs를 이용하여 1~4를 수행한다.

알게된 점

각각의 명령어 D, S, L, R를 어떻게 저장해야하나 했는데 달고 다니면 되는 거였다. 이전꺼에 명령어를 문자열로 붙여서 큐에 함께 넣으면 된다.

• 3,4번 자릿수 회전시키는 부분에서 문자열로 바꿔서 수행하고 format으로 4자리를 맞춰주니 시간초과가 난다.
  • 왼쪽으로 이동 : 1000으로 나눈 나머지에 10을 곱해서 네자리를 만들고 1000으로 나눈 몫을 더한다.
  • 오른쪽으로 이동 : 10으로 나눈 나머지에 1000을 곱해서 네자리를 만들고 10으로 나눈 몫을 더한다.

주의할 점

pypy로 제출하지 않으면 시간초과를 피할 수 없다.

코드

from collections import deque
import sys

def bfs(visited, s, e):
    visited[s] = 1
    q = deque()
    ans = ''
    q.append((s, ans))

    while q:
        x, ans = q.popleft()
        if x == e:
            return ans

        if 2*x > 9999:
            nx = (2*x)%10000
            if visited[nx] == 0:
                visited[nx] = 1
                q.append((nx, ans+'D'))

        if x==0 and visited[9999] == 0: 
            visited[9999] = 1
            q.append((9999, ans+'S'))
            
        if 2*x <= 9999 and visited[2*x] == 0:
            visited[2*x] = 1
            q.append((2*x, ans+'D'))

        if 0<=x-1<10000 and visited[x-1] == 0:
            visited[x-1] = 1
            q.append((x-1, ans+'S'))

        nx = int((x%1000)*10 + x/1000)
        if nx<10000 and visited[nx] == 0:
            visited[nx] = 1
            q.append((nx, ans+'L'))

        nx = int((x%10)*1000 + x/10)
        if nx<10000 and visited[nx] == 0:
            visited[nx] = 1
            q.append((nx, ans+'R'))

n = int(input())
for _ in range(n):
    s, e = map(int, sys.stdin.readline().split())
    visited = [0]*10000 
    print(bfs(visited, s, e))