[백준] 9019 파이썬(python) : DSLR - (★)

9019번: DSLR

 

 

 

import sys
from collections import deque
t = int(sys.stdin.readline())
for _ in range(t):
    a, b = map(int, sys.stdin.readline().split())
    q = deque()
    q.append((a, "")) #1
    visit = [False]*10001
    while q:
        num, path = q.popleft()
        visit[num] = True
        if num == b: #2
            print(path)
            break
        num2 = (num*2)%10000 #3
        if not visit[num2]:
            q.append((num2, path+"D"))
            visit[num2] = True
        
        num2 = (num-1)%10000 #4
        if not visit[num2]:
            q.append((num2, path+"S"))
            visit[num2] = True
        num2 = (10*num+(num//1000))%10000 #5
        if not visit[num2]:
            q.append((num2, path+"L"))
            visit[num2] = True
        
        num2 = (num%10)*1000+(num//10) #6
        if not visit[num2]:
            q.append((num2, path+"R"))
            visit[num2] = True

 

#1 : 처음 시작하는 값

#2 : 탈출조건

#3 : D를 실행하고 방문하지 않았으면 방문처리 밑 큐에 D가 추가된  path입력

#4 : S를 실행

#5 : L을 실행하기 위해 연산자 조작

#6 : R 실행

 

위의 풀이 수정)

import sys
from collections import deque
t = int(sys.stdin.readline())
func = [ "D", "S", "L", "R" ]
for _ in range(t):
    a, b = map(int, sys.stdin.readline().split())
    visit = [False] * 10001
    def bfs():
        q = deque()
        q.append((a, ""))
        while q:
            num, path = q.popleft()
            if num == b:
                print(path)
                return
            visit[num] = True
            for i in func:
                if i == "D":
                    num2 = (num*2)%10000
                    if visit[num2] == False: 
                        visit[num2] = True
                        q.append((num2, path+"D"))
                elif i == "S":
                    num2 = ((num-1)+10000)%10000
                    if visit[num2] == False:
                        visit[num2] = True
                        q.append((num2, path+"S"))
                elif i == "L":
                    num2 = (num%1000)*10 + (num//1000)
                    if visit[num2] == False:
                        visit[num2] = True
                        q.append((num2, path+"L"))
                else:
                    num2 = (num%10)*1000 + (num//10)
                    if visit[num2] == False:
                        visit[num2] = True
                        q.append((num2, path+"R"))
    bfs()

 

조금 더 오래걸리는 풀이이긴 하지만 시간제한이 6초니까 넉넉하다.