[백준 9019번] DLSR - python

문제 링크

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

9019번: DSLR

풀이 

- 시간 초과 해결 하느라 시간이 오래 걸렸다. 

- 원래는 B와 같아지면 함수 내에서 출력하고 break을 실행했는데, return 으로 값을 전달받고 출력하니 해결되었다. 

- A와 B는 0보다 크거나 같고 10000보다 작으므로 visites = [False] * 10000 에 방문 표시를 해준다. 

- 큐에는 숫자와 지금까지 실행한 명령어가 들어간다. 

bfs(num)를 실행하면 num의 방문표시를 하고, num이 B와 같으면 명령어 리턴하고 출력 

1. num * 2 가 9999보다 크고, (num*2) %10000를 방문하지 않았으면 (num*2) %10000과 명령어에 "D"를 추가하여 큐에 삽입, 방문 표시 

   num * 2가 9999보다 작거나 같고, num * 2 를 방문하지 않았으면, num * 2와 명령어에 "D"를 추가하여 큐에 삽입, 방문 표시 

2. num 이 0이고 9999를 방문하지 않았으면 9999와 명령어에 "S"를 추가하여 큐에 삽입, 방문 표시

    num이 0이 아니고 num -1를 방문하지 않았으면 num-1와 명령어에 "S"를 추가하여 큐에 삽입, 방문 표시

3. 각 자릿수를 오른편 회전시킨 숫자 nx = int((num%1000)*10 + num / 1000) 

nx 를 방문하지 않았으면 nx와 명령어에 "R"를 추가하여 큐에 삽입, 방문 표시 

4. 각 자릿수를 오른편 회전시킨 숫자 ny = int((num%10)*1000 + num / 10)

ny 를 방문하지 않았으면 ny와 명령어에 "L"를 추가하여 큐에 삽입, 방문 표시

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

t = int(input())

def bfs(s):
  
  visited[s] = True
  
  q = deque()
  q.append((s,""))
  
  while q:
    num, c = q.popleft()
    if num == b:
      return c
      
    if num * 2 > 9999 :
      if not visited[(2* num) % 10000] :
        visited[(2* num) % 10000] = True
        q.append(((2* num) % 10000 , c +"D" ))
    else :
      if not visited[num*2]:
        visited[num*2] = True
        q.append((num*2 , c+"D"))

    if num == 0:
      if not visited[9999]:
        visited[9999] = True
        q.append((9999, c + "S"))
    else :
      if not visited[num-1]:
        visited[num-1] = True
        q.append((num - 1 , c + "S"))

    nx = int((num%1000)*10 + num / 1000)
    ny = int((num%10)*1000 + num / 10)
    if num != 0:
      if not visited[nx]:
        visited[nx] = True
        q.append((nx, c + "L"))
    
      if not visited[ny]:
        visited[ny] = True
        q.append((ny, c + "R"))

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