💻 백준 9019번: DSLR

문제 소개 🧐

네 개의 명령어(D, S, L, R)를 사용하는 계산기에서, 주어진 숫자 A를 다른 숫자 B로 바꾸는 최소한의 명령어 순서를 찾는 문제입니다.

  • D (Double): n을 2배로 만들고 10000으로 나눈 나머지를 저장합니다.
  • S (Subtract): n에서 1을 뺍니다. (0일 경우 9999 저장)
  • L (Left Rotate): n의 네 자릿수를 왼쪽으로 회전시킵니다. (1234 -> 2341)
  • R (Right Rotate): n의 네 자릿수를 오른쪽으로 회전시킵니다. (1234 -> 4123)

입력 📝

  • 첫 줄에 테스트 케이스의 수 T가 주어집니다.
  • 각 테스트 케이스마다, 공백으로 구분된 두 정수 A와 B가 주어집니다. (0 <= A, B < 10000)

출력 📤

  • A를 B로 바꾸는 가장 짧은 명령어 조합을 출력합니다.

제한 ❌

  • 시간: 6초
  • 메모리: 256MB

첫 번째 시도: BFS와 문자열 연산 👊

Idea

BFS를 사용하여 가능한 모든 명령어 조합을 탐색한다. 각 숫자는 노드, 명령어는 간선으로 생각할 수 있다. L과 R 연산은 파이썬의 문자열 슬라이싱을 활용하여 구현하고, 방문한 숫자를 기록하여 중복 탐색을 피한다.

Code

import sys
from collections import deque

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

def op_S(n:int):
    if n == 0:
        return 9999
    return n - 1

def op_L(n:int):
    n_str = str(n).rjust(4, '0')
    new_n_str = n_str[1:] + n_str[0]
    return int(new_n_str)

def op_R(n:int):
    n_str = str(n).rjust(4, '0')
    new_n_str = n_str[-1] + n_str[:-1]
    return int(new_n_str)

def solve():
    A, B = map(int, sys.stdin.readline().split())
    queue = deque([(A, "")])
    visited = {A}

    while queue:
        cur_num, path = queue.popleft()

        if cur_num == B:
            print(path)
            return

        # D
        next_d = op_D(cur_num)
        if next_d not in visited:
            visited.add(next_d)
            queue.append((next_d, path + 'D'))

        # S
        next_s = op_S(cur_num)
        if next_s not in visited:
            visited.add(next_s)
            queue.append((next_s, path + 'S'))

        # L
        next_l = op_L(cur_num)
        if next_l not in visited:
            visited.add(next_l)
            queue.append((next_l, path + 'L'))

        # R
        next_r = op_R(cur_num)
        if next_r not in visited:
            visited.add(next_r)
            queue.append((next_r, path + 'R'))

t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    solve()

Result

  • 시간 초과: 문자열 변환 및 처리 과정에서 발생하는 오버헤드가 커서 시간 제한을 초과하는 것 같다. 특히 L, R 연산과 visited 셋에서의 확인 과정이 시간이 꽤 걸리는 것 같았다.

두 번째 시도: BFS 최적화 (산술 연산 및 경로 역추적) ✨

Idea

문자열 연산을 산술 연산으로 대체하여 L, R 명령어의 성능을 개선한다. 또한, 매번 큐에 경로 문자열 전체를 저장하는 대신, parent 배열을 만들어 어떤 숫자로부터 현재 숫자가 만들어졌는지, 그리고 어떤 연산이 사용되었는지를 기록해서. 목표 숫자에 도달하면, parent 배열을 역추적하여 최종 경로를 구성한다.

Code

import sys
from collections import deque

def solve():
    A, B = map(int, sys.stdin.readline().split())
    queue = deque([A])
    # visited[i] = (이전 숫자, 사용된 명령어)
    visited = {A: (None, None)} 

    while queue:
        cur_num = queue.popleft()

        if cur_num == B:
            path = ''
            # 역추적하여 경로 생성
            while cur_num != A:
                prev_num, op = visited[cur_num]
                path = op + path
                cur_num = prev_num
            print(path)
            return

        # D
        next_d = (cur_num * 2) % 10000
        if next_d not in visited:
            visited[next_d] = (cur_num, 'D')
            queue.append(next_d)

        # S
        next_s = (cur_num - 1) if cur_num != 0 else 9999
        if next_s not in visited:
            visited[next_s] = (cur_num, 'S')
            queue.append(next_s)

        # L
        next_l = (cur_num % 1000) * 10 + (cur_num // 1000)
        if next_l not in visited:
            visited[next_l] = (cur_num, 'L')
            queue.append(next_l)

        # R
        next_r = (cur_num % 10) * 1000 + (cur_num // 10)
        if next_r not in visited:
            visited[next_r] = (cur_num, 'R')
            queue.append(next_r)

t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    solve()

Result

  • 시간 초과 (Python 3), 정답 (PyPy3): 첫 번째 시도보다 훨씬 빨라졌지만, Python 3에서는 여전히 시간 제한을 통과하지 못했다. PyPy의 JIT 컴파일러가 반복적인 연산을 더 효율적으로 처리하기 때문에 PyPy에선 통과할 수 있었다.

개선할 부분 🤔

  • Python 3 통과를 위한 최적화: Python 3로 통과하기 위해서는 더 적합한 알고리즘을 찾아 적용해야겠다. 현재 코드에서 Python의 성능 한계를 느꼈다.
  • 코드 가독성: 각 연산을 별도의 함수로 분리하면 가독성을 더 높일 수 있지만, BFS 루프 내에 직접 구현하는 것이 약간의 성능 이점을 가질 수 있을 것 같다.
⁂