[백준] 9019번: DSLR

문제

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

9019번: DSLR

 

풀이

BFS(너비 우선 탐색)를 사용해 풀었습니다.

큐에 (현재 숫자, 명령어)를 저장합니다.

시간 초과가 발생하지 않게 check를 사용해 이전에 이미 확인한 숫자면 다시 확인하지 않도록 합니다.

※ 처음에 L, R 연산을 큐를 사용해 이동시켰더니 시간 초과가 발생하여 단순 계산으로 바꿨더니 해결되었습니다.

 

코드

파이썬

from collections import deque
import sys

input = sys.stdin.readline


def BFS():
    queue = deque()
    check = [False] * 10000
    check[A] = True
    queue.append((A, ""))
    while queue:
        n, pro = queue.popleft()

        if n == B:
            return pro
        
        # D
        nn = n * 2
        if nn > 9999:
            nn %= 10000
        if not check[nn]:
            check[nn] = True
            queue.append((nn, pro + "D"))

        # S
        nn = n - 1
        if nn < 0:
            nn = 9999
        if not check[nn]:
            check[nn] = True
            queue.append((nn, pro + "S"))

        # L
        nn = ((n % 1000) * 10) + (n // 1000)
        if not check[nn]:
            check[nn] = True
            queue.append((nn, pro + "L"))

        # R
        nn = ((n % 10) * 1000) + (n // 10)
        if not check[nn]:
            check[nn] = True
            queue.append((nn, pro + "R"))


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