📖 백준 - 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 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.

S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.

L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.

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로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

📌 예제

입력

3
1234 3412
1000 1
1 16

출력

LL
L
DDDD

📌 풀이 및 해설

처음 숫자를 입력받고 4가지로 변환되는 모든 경우를 탐색하여 결과를 찾아낸다. 즉 4가지의 경우를 찾기 위해서는 완전 탐색 기법을 이용한다면 문제를 해결 할 수 있다.

완전 탐색 기법을 이용하는데, 만약 처음 입력 받은 수가 1234라면
1. L 방법의 경우 2341
2. R 방법의 경우 4123
3. D 방법의 경우 2468
4. S 방법의 경우 1233

으로 만들 수 있는데, 이렇게 생성 된 수가 찾고자 하는 수와 일치한다면, 탐색을 중단하고 이용한 방법을 출력하게끔 만든다.

탐색 방법에는 BFS가 적당하다고 생각하는데, DFS를 사용하기에는 한가지 방법만으로 끝까지 탐색하고 그다음 방법을 이용하므로 4가지 방법을 순서대로 탐색을 시도하는 BFS보다는 시간이 오래 걸릴 수 있다고 생각한다.

정리하자면, BFS 방법을 이용한 완전 탐색 기법을 이용하여 탐색을 시도한다.

📌 소스코드

from collections import deque
import sys

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

def S_control(n):
    res = n
    if n == 0:
        res = 9999
        return res
    res -= 1
    return res

def L_switch(n):
    front = n % 1000
    back = n // 1000
    res = front*10 + back
    return res

def R_switch(n):
    front = n % 10
    back = n // 10
    res = front*1000 + back
    return res


def bfs(A,B):
    que = deque()
    que.append((A,""))
    visited = set()
    visited.add(A)
    while que:
        number, command = que.popleft()
        if number == B:
            print(command)
            return

        tmp = D_control(number)
        if tmp not in visited:
            visited.add(tmp)
            que.append((tmp,command+"D"))

        tmp = S_control(number)
        if tmp not in visited:
            visited.add(tmp)
            que.append((tmp,command+"S"))

        tmp = L_switch(number)
        if tmp not in visited:
            visited.add(tmp)
            que.append((tmp,command+"L"))

        tmp = R_switch(number)
        if tmp not in visited:
            visited.add(tmp)
            que.append((tmp,command+"R"))


T = int(sys.stdin.readline())
for i in range(T):
    A,B = map(int,sys.stdin.readline().split())
    bfs(A,B)

📌 후기

BOJ 그래프 탐색 문제 중 하나,
해당 문제를 어떻게 풀 지 생각할 때, BFS를 이용하는 방법까지는 생각했으나, 입력 숫자를 바꾸는 과정에서 문자열을 이용하는 방법을 생각하고 이용하였으나 시간초과가 발생하였다.

따로 해결 방법을 생각하지 못해서 해당 부분은 직접 해결하지 못했다. 따로 문자형 변환 없이, 정수형으로만 해결할 수 있는 방법을 알게 되었다.

그리고 visited 또한 4배씩 증가하므로, 5번만 탐색을 진행해도 약 1000개가 넘는 중간 이동 숫자가 쌓일 수 있다. 그러므로, visited를 리스트로 사용하여 존재 여부를 사용하는 순간 O(N)이 소모되므로 시간 초과 문제가 발생하였다. 이 부분도 해시(Dict)를 이용하여 해결해보려고 했으나 코드가 복잡해지면서 실패, 파이썬의 set을 이용할 수 있음을 다른 풀이에서 볼 수 있었다.

set 자료형 또한 dictionary처럼 중복 처리를 자동으로 할 수 있고 해시기반이라서 O(1)의 성능을 낼 수 있음을 알게 되었다.
수를 이용한 여러가지 구현 방법, 자료형에 대한 더 높은 이해가 필요할 것 같다.