알고리즘/백준[baekjoon]

[baekjoon] 백준 9019번 : DSLR (by python) bfs *pypy3

코딩하는이씨 2022. 7. 2. 16:55
728x90
반응형

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

 

9019번: DSLR

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

www.acmicpc.net

 

정답 code

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

t = int(input())
for _ in range(t):
    a,b = map(int,input().split())
    q = deque()
    q.append((a,""))
    visit = [False]*10000

    while q:
        num, path = q.popleft()
        visit[num] = True
        if num == b:
            print(path)
            break

        num2 = (2*num)%10000
        if not visit[num2]:
            visit[num2] = True
            q.append((num2,path+"D"))

        num2 = (num-1)%10000
        if not visit[num2]:
            visit[num2] = True
            q.append((num2,path+'S'))

        num2 = (10*num+(num//1000))%10000
        if not visit[num2]:
            visit[num2] = True
            q.append((num2,path+'L'))

        num2 = (num//10+(num%10)*1000)%10000
        if not visit[num2]:
            visit[num2] = True
            q.append((num2,path+"R"))

 

solution

bfs를 이용하여 해결하면 되는문제이다.

시작하는 A수를 queue에 넣고 D,S,L,R을한 수를 순서대로 찾아가며 경로를 저장한다.

경로를 저장하기위해 path에 D,S,L,R을 추가해 가며 A로부터 어떤경로로 해당 수에 도달했는지 저장한다.

 

각자리수를 왼편과 오른편으로 회전시키는 경우는 문자열로 분리하는것이 아닌 수식으로 해결하였다.

 

728x90
반응형