[BOJ] 9019번 DSLR

링크: https://www.acmicpc.net/problem/9019

---

문제 이해

이 문제를 처음 접했을 때, 내 머리는 이런 식으로 이해했다.
 
레지스터 \( n \) \( (0 \le n \le 10\,000) \) 이 있다. 그리고 명령어가 존재한다. 이는 D, S, L, R로 나뉜다.
그리고 \( n \)의 네 자릿수를 \( d_1, d_2, d_3, d_4 \) 라고 한다.
\( n = ((d_1 * 10 + d_2) * 10 + d_3) * 10 + d_4 \) 이다. 쉽게 이야기하면, \(d_i\)는 \(i\) 번째 수라 보면 된다. \( ( 1 \le i \le 4 ) \)

 
명령어 D, S, L, R은 다음과 같다.
D: \( 2n \bmod 10\,000 \)
S: \( n - 1 \) (만약 계산된 결과가 음수라면 \( n = 9\,999 \))
L: \(d_2\) \(d_3\) \(d_4\) \(d_1\)
R: \(d_4\) \(d_1\) \(d_2\) \(d_3\)
 
\(A\)와 \(B\)가 주어진다, \(A\)에서 \(B\)로 변환하기 위해 필요한 최소한의 명령어를 출력해야 하는 문제이다.
당연하게도 조건은 \(0 \le A, B \le 10\,000\) 일 거다.

---

첫 번째 시도

사실 이 문제의 접근법이 바로 떠오르지 않았다.
그래서 처음에는 무지성 재귀를 이용해 풀기로 하였다.

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

def DSLR(current_num, history):
    if current_num == B:
        return history

    D = current_num * 2 % 10_000

    S = current_num - 1
    if S == 0: S = 9999

    d1, d2 = divmod(current_num, 1000)
    d2, d3 = divmod(d2, 100)
    d3, d4 = divmod(d3, 10)
    L = d2 * 1000 + d3 * 100 + d4 * 10 + d1
    R = d4 * 1000 + d1 * 100 + d2 * 10 + d3

    D = DSLR(D, history + "D")
    S = DSLR(S, history + "S")
    L = DSLR(L, history + "L")
    R = DSLR(R, history + "R")

    return min(
        (len(D), D),
        (len(S), S),
        (len(L), L),
        (len(R), R)
    )[0]

T = int(input())

for _ in range(T):
    A, B = map(int, input().split())
    print(DSLR(A, ""))

이 코드는 DSLR 각 명령어에 대한 정보를 탐색하여 \(A\)에서 \(B\)가 될 때까지 함수를 계속 호출하는 형식이다.
사실 코드가 제대로 작동할지는 모르겠고, 딱 봐도 TLE가 나올 것같이 생긴 코드라서 어떻게 해야 최적화를 할 수 있을지 고민했다.

---

두 번째 시도

단순하게 \(A\) -> \(B\) 로 변환할 때 단순하게 생각해 보기로 했다.
만약 명령어 S (\(n - 1\)) 를 계속한다면 \(n\) 의 범위에 의해 \(9\,999\) 번 걸린다는 걸 알았다.
이런 식이면 위 재귀에서 중복되는 호출을 없앨 수 있다는 확신과 어차피 \(n\)에서 한번 명령어를 입력했을때 변화된 \(n\)의 명령어는 무조건 최소라는 게 떠올라서 bfs로 접근하기로 했다.

from collections import deque
import sys

input = sys.stdin.readline

def DSLR(cur_num):
    D = cur_num * 2 % 10_000

    S = cur_num - 1
    if S == 0: S = 9999

    d1, d2 = divmod(cur_num, 1000)
    d2, d3 = divmod(d2, 100)
    d3, d4 = divmod(d3, 10)
    L = d2 * 1000 + d3 * 100 + d4 * 10 + d1
    R = d4 * 1000 + d1 * 100 + d2 * 10 + d3

    return (D, S, L, R)

keywords = ["D", "S", "L", "R"]
T = int(input())

for _ in range(T):
    A, B = map(int, input().split())

    queue = deque([A])
    visited = [""] * 10_000

    while queue and not visited[B]:
        num = queue.popleft()

        for i, n in enumerate(DSLR(num)):
            if not visited[n]:
                visited[n] = visited[num] + keywords[i]
                queue.append(n)

    print(visited[B])

그대로 구현하고 Python3로 제출하니 TLE가 뜨는 것이다.
아, CPython이 느려서 TLE가 뜨는거라 생각하고 PyPy3로 제출해 봤다.
? 이번엔 WA가 떴다.
TLE가 아닌 WA가 뜬 이상 내 코드가 문제 해결과는 거리가 멀다는 소리가 된다.
구상엔 문제가 없다 확신하고 다시 문제를 읽어보았다.

---

세 번째 시도

첫 번째 코드와 두 번째 코드에서 무언가 이상한 점이 하나 보인다. 그건 바로 S의 계산 방식이다.
이건 내가 이해한 것과는 반대로 S를 계산하는 코드에선 S가 \(-1\) 이 튀어나오는 괴현상이 존재한다.
그 이유는 S가 \(0\) 일 때, \(9\,999\) 로 설정해 주었기 때문이다.
 
그리고 bfs에서 visited를 처리하는 방식이 문제가 있다.
왜냐하면 처음 \(A\)의 입장에서는 방문 표시를 하지 않기 때문에, 저기서 누적으로 다른 값에 접근해 버릴 수 있게 된다.
그래서 visited[n] 처리와 함께 n == A를 두어서 해결하였다.

사실 크리티컬한 문제는 S의 계산 이슈지만, visited도 고치면 로직이 더 정확해지니 고쳤다.

from collections import deque
import sys

input = sys.stdin.readline

def DSLR(num):
    D = (num * 2) % 10_000

    S = num - 1
    if S == -1: S = 9_999

    d1, d2 = divmod(num, 1_000)
    d2, d3 = divmod(d2, 100)
    d3, d4 = divmod(d3, 10)
    L = d2 * 1_000 + d3 * 100 + d4 * 10 + d1
    R = d4 * 1_000 + d1 * 100 + d2 * 10 + d3

    return (D, S, L, R)

keywords = ["D", "S", "L", "R"]
T = int(input())

for _ in range(T):
    A, B = map(int, input().split())

    queue = deque([A])
    visited = [""] * 10_000

    while queue and not visited[B]:
        num = queue.popleft()

        for i, n in enumerate(DSLR(num)):
            if not (visited[n] or n == A):
                visited[n] = visited[num] + keywords[i]
                queue.append(n)

    print(visited[B])

PyPy3 AC!

격자가 주어진 상태에서만 bfs를 썼던 것과는 다르게 새로운 시각에서 접근할 수 있어 신선한 경험이었다.
Python3로도 통과한 사람이 있는걸 보면 나는 아직 배울게 많아보인다. 더 꾸준히 해야겠다는 생각도 들었다.