코테/BOJ

백준 9019 [DSLR] 파이썬

동 캄 2022. 4. 18. 11:18
반응형

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

 

9019번: DSLR

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에

www.acmicpc.net

# 백준 9019 DSLR
from collections import deque
import sys
input = sys.stdin.readline


def bfs(start, end):
    q = deque([])
    q.append((start, ''))
    move = ''
    while q:
        start, move = q.popleft()
        D = (start*2) % 10000
        if D == end:
            return move+'D'
        elif visited[D] == 0:
            visited[D] = 1
            q.append((D, move+'D'))

        S = 9999 if start == 0 else start-1
        if S == end:
            return move+'S'
        elif visited[S] == 0:
            visited[S] = 1
            q.append((S, move+'S'))

        L = (start % 1000)*10+start // 1000
        if L == end:
            return move+'L'
        elif visited[L] == 0:
            visited[L] = 1
            q.append((L, move+'L'))
        R = (start % 10)*1000+start//10
        if R == end:
            return move+'R'
        elif visited[R] == 0:
            visited[R] = 1
            q.append((R, move+'R'))


for _ in range(int(input())):
    start, end = map(int, input().split())
    visited = [0]*(10000)
    answer = bfs(start, end)
    print(answer)

bfs로 생각하는게 어려운 문제였다. visited를 이용하여 방문확인 여부를 따진다.

반응형