[백준 BOJ_9019] DSLR Python 풀이

출처: 백준 온라인 저지

문제

풀이

최소 경로를 찾아야 하기 때문에 BFS를 이용하여 풀어주었습니다.

우선 dq에 시작하는 수인 A와 빈 배열을 넣어줍니다. 후에 명령어가 추가되면 빈 배열에 명령어를 추가해줍니다.
이미 방문한 수에는 방문하지 않게끔 정수의 범위인 0부터 10,000 미만까지로 visited를 만들어줍니다.

dq.popleft()를 사용하여 현재 정수인 src와 여태까지의 명령어인 cmd를 받아주고, src가 우리가 만들고자 하는 정수 B와 같다면 result를 가장 짧은 값으로 update해줍니다.

같지 않다면 문제에서 제시한 4가지의 경우의 수로 src를 변환하였을 때, 변환한 정수를 방문한 적이 없다면 dq에 명령어를 추가해준 cmd와 함께 추가해줍니다.

반복해준 뒤 result를 출력해줍니다.

코드

from collections import deque
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
  A, B = input().rstrip().split()
  result = ""
  dq = deque([(A, "")])
  visited = [ 0 for _ in range(10000)]
  while dq:
    src, cmd = dq.popleft()
    if src == B:
      result = cmd if len(result) > len(cmd) or not result else result
    elif not result or (result and len(cmd) < len(result)):
      if len(src) < 4:
        src = "0"*(4-len(src)) + src
      D, S, L, R = int(src)*2%10000, int(src)-1 if int(src) > 0 else 9999, int(src[1:]+src[0]), int(src[3]+src[:3])
      if not visited[D]:
        dq.append((str(D), cmd+"D"))
        visited[D] = 1
      if not visited[S]:
        dq.append((str(S), cmd+"S"))
        visited[S] = 1
      if not visited[L]:
        dq.append((str(L), cmd+"L"))
        visited[L] = 1
      if not visited[R]:
        dq.append((str(R), cmd+"R"))
        visited[R] = 1
  print(result)