백준 9019번: DSLR [python]

tomkitcount·2025년 7월 22일

매일 알고리즘

목록 보기

130/290

난이도 : 골드 4
유형 : BFS, 역추적
https://www.acmicpc.net/problem/9019

문제 이해

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

=> n은 네자리 이하의 수.
n이 1234 면
d1 = 1, d2 = 2, d3 = 3, d4 = 4 이다.

D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.

S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.

L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
-> 1234 를 L연산하면 2341 이 됨

R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.
-> 1234 를 R연산하면 4123 이 됨

위에서 언급한 것처럼, 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로 가는 최단 경로를 찾아야 한다 → BFS
방문한 숫자는 다시 방문할 필요 없다. → visited 배열 필요
어떤 경로(연산)를 통해 도착했는지도 저장해야 한다. → prev 배열

큐를 사용한 BFS를 돌린다.
visited[0~9999] 로 숫자를 방문했는지 관리.
from[0~9999] 와 how[0~9999] 를 써서,

from[x] = y : x로 오기 전의 숫자 y
how[x] = 연산문자 : y에서 x로 올 때 어떤 연산을 썼는지

BFS가 끝나면 B부터 역추적하면서 연산 순서를 복원.

이때 최단 경로의 길이뿐만 아니라, 실제 연산 순서를 출력해야 하므로.
따라서 BFS를 돌릴 때 각 상태가 어디서 왔는지(from_num)와
어떤 연산으로 왔는지(how)를 기록해두고, 목표 B에 도착한 뒤 거꾸로 추적하는게 핵심이다.

해답 및 풀이

import sys
from collections import deque
input = sys.stdin.readline

# D, S, L, R 연산 함수
def next_states(x):
    return [
        ('D', (2*x) % 10000),
        ('S', 9999 if x == 0 else x - 1), # x가 0이라면 9999, 아니라면 x-1 연산
        ('L', (x % 1000) * 10 + x // 1000), # L 연산
        ('R', (x // 10) + (x % 10 ) * 1000), # R 연산
    ]


def bfs(start, target): 
    visited = [False] * 10000 # 아직 방문하지 않았으면 False, 방문 시 True
    from_num = [-1] * 10000  # 어디서 왔는지, -1로 초기화
    how = [''] * 10000 # 어떻게 왔는 지

    q = deque()
    q.append(start)
    visited[start] = True

    while q:
        now = q.popleft()
        if now == target:
            break

        for command, nxt in next_states(now):
            if not visited[nxt]:
                visited[nxt] = True
                from_num[nxt] = now
                how[nxt] = command
                q.append(nxt)

    # 역추적
    result = []
    current = target
    while current != start:
        result.append(how[current])
        current = from_num[current]
    result.reverse()
    return ''.join(result)            

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

L 연산

1234 를 왼쪽으로 돌리는 L 연산을 하면 2341이 된다.
이를 연산화 하려면
1234를 1000으로 나눈 나머지 234를 10 곱해주고, (2340)
그리고 1234에 첫째자리 1을 1000나누어 주어 1로 만든 뒤 더해주면 된다.

        (x % 1000) * 10 + x // 1000
        
        (x % 1000) * 10  # x를 1000으로 나눈 나머지 * 10 = 2340
        + # 더하기 
        x // 1000     # x를 1000으로 나누어 1의자리로 만든 값   =1      

		# 1234 -> 2341