[파이썬/Python] 백준 9019번: DSLR

📌 문제 : 백준 9019번

---

📌 문제 탐색하기

T : 테스트케이스 수
A : 레지스터 초기 값 ($0 ≤ A < 10,000$)
B : 레지스터 최종 값 ($0 ≤ B < 10,000$)

문제 풀이

4가지의 계산을 통해 A를 B로 변환하는데 필요한 최소한의 명령어 나열을 출력하는 문제이다.

⌨️ 명령어 정리

• n = 저장된 숫자
• D
  • n 2배
  • 결과가 9999보다 크다면 10000으로 나눈 나머지 값 저장
    • 2n mod 10000
• S
  • n에서 1 빼기
  • n == 0이라면
    • 9999가 대신 저장
• L
  • 각 자릿수 왼편으로 회전
  • d1, d2, d3, d4 → d2, d3, d4, d1
  • 천의 자리의 숫자를 구하고 나머지 자리들은 10만 곱해서 더해준다.
• R
  • 각 자릿수 오른편으로 회전
  • d1, d2, d3, d4 → d4, d1, d2, d3
  • 일의 자리수에 1000을 곱해주고 나머지 자리는 10을 나눠서 더해준다.
• ⚠️ 주의
  • n이 네자리 수가 아닐 경우
  • L, R 구하는 수식에서 이 부분이 커버 가능하다.

위의 명령어를 수행하면서 최소한의 명령어를 생성하는 경우를 찾는다.
→ BFS를 활용한다!!

BFS

• 만들 수 있는 최대 숫자 개수는 10000이므로 그정도 크기의 방문 리스트 정의
• 큐 정의해 현재 레지스터에 있는 숫자와 기록할 명령어 추가
• B가 될 때까지 반복
• D, S, L, R 계산 구현해 조건에 따라 값을 얻어 큐에 추가

가능한 시간복잡도

bfs 수행 → $O(4 * N)$

최종 시간복잡도
$O(4N)$로,최악의 경우 $O(40000)$이 되어 제한 시간 6초 내에 연산이 가능하다.

알고리즘 선택

4가지 계산 방법에 대해 BFS 수행

---

📌 코드 설계하기

1. 테스트케이스 입력
2. A, B 입력
3. 방문리스트 정의
4. 큐 정의
5. 방문 처리
6. 큐가 빌 때까지 반복
   6-1. B가 됐는지 확인 후 출력
   6-2. D 계산
   6-3. S 계산
   6-4. L 계산
   6-5. R 계산

---

📌 시도 회차 수정 사항

1회차

• 반복 불가능한 int 객체를 풀 수 없다는 에러가 발생했다.
• 큐를 정의할 때 queue = deque((A, ""))로 괄호를 빼먹어서 발생한 문제였다.
• 입력하고자 하는 변수 갯수는 1개인데 현재 변수 갯수가 2개 여서 값을 할당할 수 없다는 의미라고 한다. 따라서 deque 사용 시 꼭 []로 묶어주어야 한다.

2회차

• Python3에서 시간초과가 발생했기래 PyPy3로 변경했더니 틀렸다는 결과가 나왔다.
• S에서 n = 0인 경우를 고려해주어야 하는데 빼먹었다.

3회차

• S를 구현하는 코드를 여러 방식으로 하다가 이전에 썼던 코드를 삭제하지 않아서 틀렸다.

		# S 계산
        if n > 0:
            S = n - 1
        else:
            S = 9999
        if not visited[S]:
            if S <= 0:      # 0이면 9999로 변경
                S = 9999

        visited[S] = True
        queue.append((S, command + "S"))

---

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline

# 테스트케이스 입력
T = int(input())

# 테스트케이스만큼 반복
for _ in range(T):
    # A, B 입력
    A, B = map(int, input().split())

    # 방문리스트 정의
    visited = [False for i in range(10001)]

    # 큐 정의
    queue = deque([(A, "")])

    # 방문 처리
    visited[A] = True

    # 큐가 빌 때까지 반복
    while queue:
        n, command = queue.popleft()

        # B가 됐는지 확인
        if n == B:
            print(command)
            break

        # D 계산
        D = (n * 2) % 10000
        if not visited[D]:
            visited[D] = True
            queue.append((D, command + "D"))

        # S 계산
        if n > 0:
            S = n - 1
        else:
            S = 9999
        if not visited[S]:
            visited[S] = True
            queue.append((S, command + "S"))

        # L 계산
        L = n // 1000 + (n % 1000) * 10
        if not visited[L]:
            visited[L] = True
            queue.append((L, command + "L"))

        # R 계산
        R = (n % 10) * 1000 + n // 10
        if not visited[R]:
            visited[R] = True
            queue.append((R, command + "R"))

• 결과