[백준] 9019번 DSLR ★★★

💡문제접근

• 브루트포스 알고리즘이 아니라 BFS 알고리즘을 이용해야한다는 것을 뒤늦게 깨달았다.
• 연산으로 가능한 경우들을 모두 찾아서 시도해보는 방법을 이용했고 방문한 값의 경우 True로 바꿔주어 방문하지 않은 값의 경우 조건문이 실행되도록 코드를 작성했다.
• 질문게시판에 있는 접근 방식을 보고 코드를 작성할 수 있었다. 다른 사람의 도움은 받지 않았지만 솔직히 이런 문제가 코딩테스트에 나온다면 풀 자신이 있을까싶다.

💡코드(메모리 : 220292KB, 시간 : 7072ms, PyPy3로 제출)

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

def BFS(a, b):
    queue = deque()
    queue.append([a, ""])
    visited = [False] * 10000
    visited[a] = True
    while queue:
        num, result = queue.popleft()
        if num == b:
            return result
        #D
        if not visited[(num * 2) % 10000]:
            visited[(num * 2) % 10000] = True
            queue.append([(num * 2) % 10000, result + "D"])
        #S
        if not visited[(num - 1)]:
            if num == 0:
                visited[9999] = True
                queue.append([9999,  result + "S"])
            else:
                visited[(num-1) % 10000] = True
                queue.append([(num - 1) % 10000, result + "S"])
        #L
        if not visited[((num % 1000) * 10 + (num // 1000)) % 10000]:
            visited[((num % 1000) * 10 + (num // 1000)) % 10000] = True
            queue.append([((num % 1000) * 10 + (num // 1000)) % 10000, result + "L"])
        #R
        if not visited[((num % 10) * 1000 + (num // 10)) % 10000]:
            visited[((num % 10) * 1000 + (num // 10)) % 10000] = True
            queue.append([((num % 10) * 1000 + (num // 10)) % 10000, result + "R"])

T = int(input())
for _ in range(T):
    a, b = map(int, input().strip().split())
    print(BFS(a, b))

💡소요시간 : 1h