[Python/파이썬] 백준 9019 - DSLR

문제 설명

 

 

입출력 예제

 

---

풀이 코드

A와 B는 모두 0 이상 10000이하의 수라고 했으므로 visited 배열의 수를 10000으로 초기화 해주었다.

그리고 방문하지 않은 수는 bfs 탐색을 시작한다.

여기서 핵심은 일반적인 bfs 문제의 dx, dy 상하좌우 이동 처럼 D, S, L, R 을 활용하는 것이다.

큰 난이도가 있는 문제는 아니라서 아래 코드와 주석을 참고하면 이해될 것이다.

참고로 테스트 케이스 반복문 때문인지 파이썬으로 제출하면 시간초과가 났고 PYPY3로 제출하니 통과할 수 있었다.

 

정답 코드

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

def applyCommand(n, command):
    if command == "D":
        # D 는 n * 2. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다
        return (n * 2) % 10000

    if command == "S":
        # S 는 n-1. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
        return (n - 1) % 10000

    if command == "L":
        # L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다.
        return (10 * n + (n // 1000)) % 10000

    if command == "R":
        # R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다.
        return (((n % 10) * 1000) + (n // 10)) % 10000

def bfs(n):
    q = deque()
    q.append((n, ""))
    visited[n] = True

    while q:
        n, result = q.popleft()

        if n == b:
            return result

        for command in commands:
            newNum = applyCommand(n, command)

            if not visited[newNum]:
                visited[newNum] = True
                q.append((newNum, result + command))

t = int(input())
commands = ["D", "S", "L", "R"]

for _ in range(t):
    a, b = map(int, input().split())
    visited = [False] * 10000

    print(bfs(a))