[골드 4] 9019번: DSLR

Original Source: 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라고 하자).

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

---

사고의 흐름

• 우선 D, S, L, R을 모두 함수로 구현한 뒤에 구현된 명령어들을 사용하면 되겠네?
• 숫자를 바꾸기 위해 어떤 연산을 실행해야 하는지 특정하기가 어렵다. 즉 그리디는 아니다.
• 숫자를 노드라고 생각하고 연산을 노드 사이를 연결하는 간선이라고 생각하면 간선의 가중치가 모두 1로 같고, 연산의 최소 횟수, 즉 노드와 노드 사이의 최단 경로를 묻고 있으므로 BFS를 써서 풀면 된다.
• 사용했던 연산 종류들을 저장하는 부분을 따로 구현해야 한다.

 

• Logic은 맞는 것 같은데 시간 초과가 계속 뜬다. bfs 함수를 더욱 단순화시켜야겠다.
• 조건문에서 현재 노드와 다음 노드의 누적 연산자 수를 비교하지 않아도 되나? 그냥 노드가 비어 있을 때만 값을 넣어 주면 되는 건가?
• 그렇네. 인접 노드들부터 먼저 탐색하니까 굳이 연산자 수를 비교하지 않아도 최소한의 연산자들이 저장되는구나. 이게 BFS의 의미네.
• 어느 부분에서 시간 초과가 뜨는지 잘 모르겠다. 다른 사람 코드를 보자.
• 찾아보니까 애초에 Python3로 이 문제를 통과한 사람 수가 적었다. 젠장…Pypy로 제출하자.
• Pypy로 제출하니까 틀렸습니다가 뜨는데, 반례를 찾아봐야겠다.
• 시작 숫자가 0일 때, 연산 D를 적용하면 다음 숫자도 0이 된다. 이때 calc_board가 비어 있으므로 calc_board[0]에 D가 입력된다. 이 부분을 처리해주니 맞았다.

내가 작성한 소스코드

import sys
from collections import deque


def bfs(start, end):
    queue = deque()
    queue.append(start)
    calc_board = [""] * 10000
    
    while queue:
        cur = queue.popleft()

        if cur == end:
            return calc_board[cur]

        next = (cur * 2) % 10000
        if calc_board[next] == "" and cur != next:
            queue.append(next)
            calc_board[next] = calc_board[cur] + "D"

        next = (cur - 1) % 10000
        if calc_board[next] == "" and cur != next:
            queue.append(next)
            calc_board[next] = calc_board[cur] + "S"

        first = cur // 1000
        next = (cur * 10) % 10000 + first
        if calc_board[next] == "" and cur != next:
            queue.append(next)
            calc_board[next] = calc_board[cur] + "L"

        fourth = cur % 10
        next = (cur // 10) + (fourth * 1000)
        if calc_board[next] == "" and cur != next:
            queue.append(next)
            calc_board[next] = calc_board[cur] + "R"


sys.stdin.readline()
for line in sys.stdin:
    start, end = map(int, line.split())
    print(bfs(start, end))

피드백

• Python에서 A  % B (A < 0) 와 같이 음수에 Mod 연산자를 사용하면 양수가 될 때까지 A에 B를 더하다가 A가 양수가 되면 Mod 연산을 적용한다. 반면 C언어는 절댓값 A에 Mod 연산을 적용한 후 - 부호를 붙인다.
• Python으로 문제를 풀면 시간 초과로 인해 막히는 경우가 많다. 이럴 때는 Pypy로 정답을 제출하거나 C++언어로 코드를 작성해야 한다. 시간 초과에 대비해 C++를 배워 놓는 것이 좋다.
• BFS를 사용하면 자동적으로 최소 횟수가 메모리에 저장되므로 조건문에서 별다른 처리를 할 필요가 없다.
• 반례를 찾을 때는 경계선의 Input부터 조사하자.