[백준 - 9019] DSLR - Python

분류: bfs, 양방향 bfs, DP(사실 dp로 보기 애매한것 같다.) /

문제

문제 링크

문제 설명

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

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

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

 

풀이

정답

import sys
from collections import deque

global dp

def test(A:int, B:int):
    global dp
    dp[A] = ''
    q = deque([A])
    while q:
        i = q.popleft()
        for cmd in 'DSLR':
            n = i
            if cmd == 'D':
                n = (n * 2) % 10000
            elif cmd == 'S':
                n = 9999 if (n==0) else n-1
            elif cmd == 'L':
                n = (n % 1000) * 10 + (n // 1000)
            elif cmd == 'R':
                n = (n % 10) * 1000 + (n // 10)
            
            cmd = dp[i] + cmd
            if n == B:
                print(cmd)
                return 
            if dp[n] is None:
                dp[n] = cmd
                q.append(n)
    print(dp[B])

def main():
    global dp
    read = sys.stdin.readline
    T = int(read())
    for _ in range(T):
        dp = [None] * 10000
        A, B = map(int, read().split())
        test(A,B)

main()

가장 먼저 떠오른 풀이는 bfs를 이용한 완전 탐색.

빈 문자열 부터 시작해 DSLR 4가지 경우에 대해 가지를 치며 뻗어나가다 B에 닿으면 루트(빈 문자열) B까지 경로 출력.

결과는? 메모리 초과.

그도 그럴 것이 트리 깊이 B까지 깊이 k에 대해 리프의 수(큐의 길이) 4^k로 지수적으로 증가한다.

n², nlogn, log, n의 시간복잡도에 대해 고민하다가 든 생각, "정답의 길이의 최대값이 9999로 정해져있다."

조건에 맞는 어떤 A, B가 주어져도 S만 연타하면 9999이하로 A에서 B로 갈 수 있다.

A에서 n으로 가는 최소 커맨드를 `dp[n]`에 저장.

BFS로 탐색하기 때문에 처음 dp에 저장한 값이 최소 이므로 저장된 값에 대한 업데이트가 없고 B를 만나는 순간 종료.

사실 dp 리스트에 계산된 값을 저장하고 중복 계산을 피한다 해도 성능은 향상 되지만 4가지로 분기해 𝛰(2^k)는 피할 수 없다.

시간 초과가 계속되어 pypy3로 제출해봤더니 통과했다. 편법을 쓴 기분이라 기분이 썩 좋진 않다.

다른 풀이들을 봐보니 A와 B에서 양쪽에서 bfs를 수행하니 python3로도 통과한 풀이가 있었다.

양쪽에서 bfs를 수행해 만나면 트리의 깊이를 반으로 줄일 수 있다. 트리의 깊이 k에 대해 4^k의 경우의 수가 생기니 k를 반으로 줄이면 전체 경우의 수를 지수적으로 줄일 수 있다.

 

- 오답 (메모리 초과)

import sys
from collections import deque

def test(A:int, B:int):
    ans = ''
    done = False
    q = deque([('', A)])
    while q:
        acc, num = q.popleft()
        for cmd in 'DSLR':
            n = num
            if cmd == 'D':
                n = n*2 % 10000
            elif cmd == 'S':
                n = 9999 if (n==0) else n-1
            elif cmd == 'L':
                n = (n * 10 + (n // 1000)) % 10000
            elif cmd == 'R':
                n = (1000 * (n % 10)) + (n // 10)
            
            tmp = acc + cmd
            if n == B:
                ans = tmp
                done = True
                break
            q.append((tmp, n))
            
        if done:
            break
    
    print(ans)

def main():
    read = sys.stdin.readline
    T = int(read())
    for _ in range(T):
        A, B = map(int, read().split())
        test(A,B)

main()