[백준 9019] DLSR (골드4) Python

https://www.acmicpc.net/problem/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이 된다.

위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →L 2341 →L 3412
1234 →R 4123 →R 3412

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

입력

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

출력

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

---

풀이

  정수 A를 B로 만들기 위한 최소 연산 횟수를 구하는 문제이다. 이때 연산은 문제에서 정의한 D, S, L, R 연산을 활용해야 한다. 그래서 D, S, L, R 연산을 하는 함수를 만든 뒤, 이 함수들의 계산 결과를 정점으로 삼는 BFS 알고리즘을 통해 A를 B로 만드는 최단 경로를 찾으면 된다.

# 백준 9019 DSLR 골드4 https://www.acmicpc.net/problem/9019
# d, s, l, r의 명령어들을 이용해서 A를 B로 만드는 최소 계산 횟수 리턴
from collections import deque
import sys

def D(n):
    n *= 2
    if n > 9999:
        n %= 10000
    return n

def S(n):
    n -= 1
    if n == -1:
        n = 9999
    return n

# L, R의 경우 deque로 바꾼 후 rotate 하면 시간 초과 발생함.
def L(n):
    # n = deque(list(str(n)))
    # n.rotate(-1)
    # n = int(''.join(n))
    # return n
    front = n % 1000
    back = n // 1000
    return front * 10 + back

def R(n):
    # n = deque(list(str(n)))
    # n.rotate()
    # n = int(''.join(n))
    # return n
    front = n % 10
    back = n // 10
    return front * 1000 + back

# BFS
def bfs(start, visited):
    q = deque()
    q.append((start, ""))
    path_dict = {0:'D', 1:'S', 2:'L', 3:'R'}
    while q:
        x, path = q.popleft()
        visited[x] = True
        if x == b:
            return path
        for i, c in enumerate([D(x), S(x), L(x), R(x)]):
            if not visited[c]:
                visited[c] = True
                q.append((c, path+path_dict[i]))

# input
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    visited = [False] * 10001
    print(bfs(a, visited))

   D, S 함수는 간단하게 구현할 수 있다. L, R 함수가 구현이 다소 까다롭다. 처음에는 deque의 rotate method를 이용하여 간단하게 구현하려고 하였으나, 이렇게 할 경우 시간초과가 발생한다. 따라서 산술 연산을 통해 구현할 필요가 있다.

  L은 1234를 2341로 만드는 연산이다. 입력 숫자 n을 1000으로 나눈 나머지 값을 맨 앞자리에 위치시키고, n을 1000으로 나눈 몫을 뒤에 덧붙이면 된다. R은 1234를 4123으로 만드는 연산이다. 입력 숫자 n을 10으로 나눈 나머지 값을 맨 앞자리에 위치시키고, 뒤에는 n을 10으로 나눈 몫을 덧붙이면 된다.

  D, S, L, R을 구현하였으면 이제 BFS 함수를 선언한다. 이때 q에는 정점의 값과 경로를 저장한다. 그리고 현재 정점 값을 가지고 D, S, L, R 을 연산한 결과를 다음에 방문할 정점으로 삼기 위해 q에 추가해준다. 이때 경로(연산방법)도 함께 추가해준다. 

  반복문을 돌다가 B를 발견하면 반복문을 종료하고 저장해 온 경로를 리턴해준다.