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

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 9019번 DSLR
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

숫자 A를 숫자 B로 바꾸기 위해 명령 D, S, L, R을 최소 횟수로 적용하는 문제입니다.

• D: n * 2 % 10000
• S: n - 1 (0이면 9999)
• L: 왼쪽 회전
• R: 오른쪽 회전

최단 명령 문자열을 요구하므로 상태(숫자 0~9999) 그래프에서 BFS를 적용합니다.

• 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

import sys; read=sys.stdin.readline
from collections import deque

q = deque([])
enQ = q.append
deQ = q.popleft

ops = ['D', 'S', 'L', 'R']

answer = []

for T in range(int(read())):
    q.clear()
    a,b=map(int,read().split())

    enQ([a,''])
    visited = set([a])

    while q:
        cur = deQ()

        for op in ops:
            tmp = cur.copy()

            if op == 'D': tmp[0] = tmp[0] * 2 % 10000
            elif op == 'S': tmp[0] = (tmp[0] - 1) % 10000
            else:
                st = '%04d'%tmp[0]
                if op == 'L': tmp[0] = int(st[1:] + st[0])
                elif op == 'R': tmp[0] = int(st[-1] + st[:-1])
                    
            if tmp[0] in visited: continue
            tmp[1] += op
            visited.add(tmp[0])
            
            enQ(tmp)
            
            if tmp[0] == b:
                answer.append(tmp[1])
                q.clear()
                break

print('\n'.join(answer))

설명

BFS로 탐색하면 처음 도달한 경로가 곧 최소 연산 경로입니다.

• 큐에 (현재값, 명령문자열)을 넣고 확장
• 방문한 값은 visited로 재방문 차단
• 목표값 B를 만들면 즉시 해당 테스트케이스 탐색 종료

상태 공간이 최대 10,000개로 고정이라 BFS가 안정적으로 동작합니다.

---

• 백준 문제풀이 전체 목록 보기

---