[Baekjoon]9019번 DSLR

문제

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

 

---

풀이

오답에서 놓쳤던 부분들

1. L과 R에서 이동할때, str로 변경하지 않고 몫과 나머지로 계산해서 구할 수 있다.

2. visited를 딕셔너리로 하는 것보다 리스트로 만들어서 인덱싱 하는 것이 더 빠르다.

3. visited를 통해 더 적은 수로 미리 만들어진 곳은 큐에 추가하지 않는다.

 

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

t = int(input())

for _ in range(t):
  visited = [False for _ in range(10001)]
  a, b = map(int, input().split())
  
  q = deque()
  q.append([a, ''])
  visited[a] = True

  while q:
    n, funs = q.popleft()
	
    if n == b:
      print(funs)
      break

    d = (n * 2) % 10000
    if not visited[d]:
      visited[d] = True
      q.append([d, funs + 'D'])

    s = (n - 1) % 10000
    if not visited[s]:
      visited[s] = True
      q.append([s, funs + 'S'])

    l = n//1000 + (n % 1000) * 10
    if not visited[l]:
      visited[l] = True
      q.append([l, funs + 'L'])

    r = n//10 + (n%10) * 1000
    if not visited[r]:
      visited[r] = True
      q.append([r, funs + 'R'])