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

문제

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

풀이

• 명령어: D, S, L, R
• n(0 ~ 9999)의 네 자릿수: d1, d2, d3, d4
  • 즉, n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4

1. D: n을 2배로 바꾼다.(n이 9999보다 큰 경우에는 10000으로 나눈 나머지)
2. S: n에서 1을 뺀 결과 n-1을 저장(n이 0이라면, 9999가 대신 저장)
3. L: n의 각 자릿수를 왼편으로 회전(d2, d3, d4, d1)
4. R: n의 각 자릿수를 오른편으로 회전(d4, d1, d2, d3)

• A를 B로 바꾸는 최소한의 명령어 출력

이 문제는 명령어의 조합으로 숫자를 바꾸는 최단 경로 문제입니다.
BFS를 사용하여 문제를 풀어 봤습니다.

각 숫자를 "정점", 명령어를 "간선"으로 이해하시면 편합니다.

def bfs(a,b):
    visited = [False] * 10000
    queue = deque([(a, "")])
    visited[a] = True # 시작 숫자 방문 처리

레지스트리에 저장될 수 있는 가장 큰 수는 9999이므로 방문 여부를 체크할 visited의 크기를 10000으로 설정해 줬습니다.

탐색을 진행할 queue에는 탐색을 할 단어(a)와 진행된 커맨드를 담아 주었습니다.

    while queue:
        cur, cmd = queue.popleft()
        
        if cur == b:
            return cmd

현재 글자와 커맨드를 출력해 탐색 시작

만약, 현재 글자가 목표 글자와 같다면 현재까지의 커맨드를 리턴

이제부터 위에 명시된 커맨드들을 모두 정의해 줍니다.

        D = (cur * 2) % 10000
        if not visited[D]:
            visited[D] = True
            queue.append((D, cmd + 'D'))

D: n을 2배로 변환
같은 숫자를 다시 방문하지 않도록 하기 위해서 현재 연산을 진행한 값이 방문하지 않았다면, 방문 처리 + 현재 연산 결과 queue에 추가

        S = cur - 1 if cur > 0 else 9999
        if not visited[S]:
            visited[S] = True
            queue.append((S, cmd + 'S'))

S: n에서 1을 뺀 결과 n-1을 저장

        L = (cur % 1000) * 10 + (cur // 1000)
        if not visited[L]:
            visited[L] = True
            queue.append((L, cmd + 'L'))

L: n의 각 자릿수를 왼편으로 회전

숫자 1234을 2341로 바꾸기 위해 값을 1000으로 나눈 나머지(234)에 1000으로 나눈 몫(1)을 붙여 주기 위해 위와 같은 식을 사용했습니다.

        R = (cur % 10) * 1000 + (cur // 10)
        if not visited[R]:
            visited[R] = True
            queue.append((R, cmd + 'R'))

R: n의 각 자릿수를 오른편으로 회전
숫자 1234를 4123으로 바꾸기 위해 값을 10으로 나눈 나머지(4)에 10으로 나눈 몫(123)을 붙여 주기 위해 위와 같은 식을 사용했습니다.

코드(PyPy3)

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

def bfs(a,b):
    visited = [False] * 10000
    queue = deque([(a, "")])
    visited[a] = True
    
    while queue:
        cur, cmd = queue.popleft()
        
        if cur == b:
            return cmd
        
        D = (cur * 2) % 10000
        if not visited[D]:
            visited[D] = True
            queue.append((D, cmd + 'D'))
        
        S = cur - 1 if cur > 0 else 9999
        if not visited[S]:
            visited[S] = True
            queue.append((S, cmd + 'S'))
        
        L = (cur % 1000) * 10 + (cur // 1000)
        if not visited[L]:
            visited[L] = True
            queue.append((L, cmd + 'L'))
            
        R = (cur % 10) * 1000 + (cur // 10)
        if not visited[R]:
            visited[R] = True
            queue.append((R, cmd + 'R'))

t = int(input())
for _ in range(t):
    a,b = map(int,input().split())
    print(bfs(a,b))