접근
이런 비슷한 문제를 당장 오늘 스터디 하면서 들었었다. 16953번이었는데 이 문항을 BFS로 풀면 꽤나 비슷하지 않을까 하는 생각을 하게 되었다. 근데 나같은 그래프 혐오론자들은 이 문항을 그리디로 해결하였기 때문에 우선 16953번부터 BFS로 해결해보기로 하였다. 아 근데 진짜 어떻게 해결하는거지...라고 생각하던 찰나 그냥 큐에 다 때려넣으면 될 것 같아서. 먼저 해결하였다. 그냥 기본적으로 큐에다가 다 저장하는 형태로 넣었고, 해결할 방법을 찾았다. 다만, 문제점이 발생하였는데 연산의 횟수만 트래킹하다 보니 이게 무슨 연산을 한건지가 저장이 안되게 되어서 하나 더 추가하기로 하였다. 처음 나왔던 풀이는 이러했다.
import sys, collections
T = int(sys.stdin.readline())
for _ in range(T):
A, B = map(int, sys.stdin.readline().split())
queue = collections.deque([(A, '')])
while queue:
x, cmd = queue.popleft()
if x == B:
print(cmd)
break
queue.append(((x * 2) % 10000, cmd + 'D'))
queue.append(((x - 1) % 10000, cmd + 'S'))
queue.append(((x // 1000) + (x % 10000) * 10, cmd + 'L'))
queue.append(((x // 10) + (x % 10) * 1000, cmd + 'R'))다만 테스트케이스에서 틀린 부분이 나와서 실제 값을 던진 결과 실수로 %10000을 안해준 부분이 문제였어서 보완해서 제출하였다.
결과는 메모리 초과 파이썬으로 제출한 사람 중 맞춘 인원들 코드의 길이가 모드 긴데 다른 분들이 최소 저보다 고티어이시길래 겸손한 마음으로 PyPy3 신 님한테 다시 코드를 올려보았다.
아오 동일한 결과 어떤 부분이 문제일까? 아니나 다를까 질문게시판을 가니 저와 같은 메모리 문제를 겪는 분들이 많았습니다. 애초에 평소 같았으면 정답률 20퍼 짜리는 쳐다도 안 보는데 클래스 3에서 마지막 남은 문제여서 그래도 해결하기 위해 고민 하였습니다. 우선 방문 조건 처리를 하라는 글들이 많아서 방문 조건 처리를 위해 arr를 설정하였습니다. 이러면 끊기는 분기(어떤 느낌인지 아시죠?)를 통해서 뭔가 개선할 수 있을 것 같았다.
import sys, collections
T = int(sys.stdin.readline())
for _ in range(T):
arr = [False for _ in range(10001)]
A, B = map(int, sys.stdin.readline().split())
queue = collections.deque([(A, '')])
while queue:
x, cmd = queue.popleft()
if x == B:
print(cmd)
break
if not arr[(x * 2) % 10000]:
arr[(x * 2) % 10000] = True
queue.append(((x * 2) % 10000, cmd + 'D'))
if not arr[(x - 1) % 10000]:
arr[(x - 1) % 10000] = True
queue.append(((x - 1) % 10000, cmd + 'S'))
if not arr[((x // 1000) + (x % 10000) * 10) % 10000]:
arr[((x // 1000) + (x % 10000) * 10) % 10000] = True
queue.append((((x // 1000) + (x % 10000) * 10) % 10000, cmd + 'L'))
if not arr[((x // 10) + (x % 10) * 1000) % 10000]:
arr[((x // 10) + (x) % 10) * 1000] = True
queue.append((((x // 10) + (x % 10) * 1000) % 10000, cmd + 'R'))
제출하니 마의 3% 메모리 초과 구간은 넘길 수 있었다. 야호! 맞췄다 
