[백준][Python]9019번(DSLR)

백준 9019번

✔️ 문제 풀이

◾ 방문 체크 하기

• 문제의 로직은 어렵지 않으나, 방문 체크를 해주지 않으면 메모리 초과가 발생함
  ※ 방문 체크를 해줘도 Python3에서는 시간 초과가 발생한다PyPy3로만 통과 가능

최종 제출 코드

import sys
from collections import deque

input = sys.stdin.readline

def d(n):
  n *= 2
  return n % 10000

def s(n):
  n -= 1
  return 9999 if n<0 else n

def l(n):
  a = n//1000
  b = n%1000
  return b*10 + a

def r(n):
  a = n//10
  b = n%10
  return b*1000 + a

def bfs(given, destination):

  visited = [0]*10000
  visited[given] = 1
  queue = deque()
  queue.append([given,""])

  while queue:

    n, command = queue.popleft()
    if n == destination:
      return command

    sv = s(n)
    if not visited[sv]:
      visited[sv] = 1
      queue.append([sv, command+'S'])

    dv = d(n)
    if not visited[dv]:
      visited[dv] = 1
      queue.append([dv, command+'D'])

    lv = l(n)
    if not visited[lv]:
      visited[lv] = 1
      queue.append([lv, command+'L'])

    rv = r(n)
    if not visited[rv]:
      visited[rv] = 1
      queue.append([rv, command+'R'])

repeat = int(input())
for i in range(repeat):
  given, destination = map(int, input().split())
  print(bfs(given, destination))