[알고리즘] 백준 9019 DSLR

기존 풀이 방법:
시간초과가 떴고, L과 R을 문자로 바꾸고 하다보니 아무래도 시간이 초과가 난 거 같다

기존 풀이:

from collections import deque
import sys
t = int(input())
for test_case in range(t):
    a, b = map(int, sys.stdin.readline().split())
    visited = [0] * 10001
    def bfs(x, lst):
        q = deque()
        q.append((x, lst))

        while q:
            x,  array = q.popleft()
            if visited[x] == 1:
                continue
            else:
                visited[x] = 1
            if x == b :
                return print("".join(map(str,array)))


            q.append(((2*x)%10000, array+['D']))
            q.append(((x-1)%10000,  array+['S']))

            n = str(x)
            if visited[int(n[1:]+n[0])] == 0:
                q.append((int(n[1:]+n[0]),  array+['L']))
            if visited[int(n[len(n)-1]+n[0:len(n)-1])] == 0:
                q.append((int(n[len(n)-1]+n[0:len(n)-1]), array+['R']))

    bfs(a,[])

정답풀이:
수학적인 방법으로 바꿔주니, 다행히 정답처리가 되었다.

from collections import deque
import sys
t = int(input())
for test_case in range(t):
    a, b = map(int, sys.stdin.readline().split())
    visited = [0] * 10001
    def bfs(x, lst):
        q = deque()
        q.append((x, lst))

        while q:
            x,  array = q.popleft()
            if x == b :
                return print("".join(map(str,array)))

            if visited[(2*x)%10000] == 0 :
                visited[(2*x)%10000] = 1
                q.append(((2*x)%10000, array+['D']))

            if visited[(x-1)%10000] == 0:
                visited[(x - 1) % 10000] = 1
                q.append(((x-1)%10000,  array+['S']))
            if visited[x//1000 + (x % 1000) * 10] == 0:
                visited[x // 1000 + (x % 1000) * 10] = 1
                q.append((x//1000 + (x % 1000) * 10,  array+['L']))
            if visited[x//10 + (x%10) * 1000] == 0:
                visited[x//10 + (x%10) * 1000] = 1
                q.append((x//10 + (x%10) * 1000, array+['R']))

    bfs(a,[])