DSLR_9019_python

여러 명령어를 수행할 수 있게 도와주는 BFS

문제

문제 접근

위 도식도처럼 A 숫자에서 D,S,L,R 명령어들을 각각 수행한뒤에 만들어지는 숫자에서 B가 만들어질 때까지 D,S,L,R 명령어를 수행하는 문제이다.

따라서 너비우선 탐색을 생각해볼 수 있다.

문제 해결

이 문제에서 시간초과가 난다면 L과 R 처리에서 날 확률이 높다.
L과 R에서 숫자를 회전하는 것은 join등을 이용해서 하게 되면 시간초과가 난다. join의 시간복잡도는 O(n)이기 때문이다.
따라서 다른 방법을 생각해봐야한다.
L = (10 now + (now // 1000)) % 10000
R = (now // 10 + (now % 10) 1000) % 10000
문제에서 숫자의 범위는 10000미만이므로 위와 같이 생각해볼 수 있다.!

이 코드를 쓰게 되면 pypy3에서만 정답처리가 된다.

전체 코드

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())

for _ in range(T):
    A, B = map(int, input().split())
    visited = [False] * 10000
    queue = deque()
    queue.append((A, ""))
    visited[A] = True
    while queue:
        now, answer = queue.popleft()
        if now == B:
            print(answer)
            break

        D = (now * 2) % 10000
        if not visited[D]:
            visited[D] = True
            queue.append((D, answer + "D"))

        S = (now - 1) % 10000
        if not visited[S]:
            visited[S] = True
            queue.append((S, answer + "S"))

        L = (10 * now + (now // 1000)) % 10000
        if not visited[L]:
            visited[L] = True
            queue.append((L, answer + "L"))

        R = (now // 10 + (now % 10) * 1000) % 10000
        if not visited[R]:
            visited[R] = True
            queue.append((R, answer + "R"))