🥚문제링크

https://www.acmicpc.net/problem/9019

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

🍳코드

PyPy3로 통과

import sys
input = sys.stdin.readline


def solve(A, B):
    # (현재 A값, 지금까지 수행한 연산)을 q에 삽입
    q = deque([(A, "")])
    visited[A] = True

    while q:
        A, dslr = q.popleft()

        if A == B:
            print(dslr)
            break

        # D
        new_A = A * 2 % 10000

        if not visited[new_A]:
            visited[new_A] = True
            q.append((new_A, dslr + "D"))

        # S
        if A == 0:
            new_A = 9999
        else:
            new_A = A - 1

        if not visited[new_A]:
            visited[new_A] = True
            q.append((new_A, dslr + "S"))

        # L
        new_A = (A % 1000) * 10 + A // 1000
        if not visited[new_A]:
            visited[new_A] = True
            q.append((new_A, dslr + "L"))

        # R
        new_A = (A % 10)*1000 + (A//10)
        if not visited[new_A]:
            visited[new_A] = True
            q.append((new_A, dslr + "R"))


T = int(input().strip())
for _ in range(T):
    # 연산 횟수를 줄이기 위해,
    # A값이 i일 때 DSLR 연산을 시도해보았다면
    # vsited[i] = True
    visited = [False]*100000
    A, B = map(int, input().split())
    solve(A, B)

🧂아이디어

탐색, BFS

1. 각 테스트케이스별로 A값이 i일 때, DSLR 연산을 시도해보았는지 체크하는 방문 리스트 visited를 만든다. 이는 같은 수에 대해 연산을 반복하지 않기 위함이다.
2. solve 함수는 BFS를 한다. 큐에 (현재 A값, 지금까지 수행한 연산 string)을 삽입한다.
   이후 큐에 담겨있던 A값에 대해 D, S, L, R 연산을 각각 수행한 뒤
   방문한 적이 없다면 방문 표시를 하고, 큐에 (연산을 수행한 뒤의 A값, 연산 string+ 현재 수행한 연산)을 삽입한다.

• (주의) L, R 연산 -> 다른 자료구조 (deque, list 등...)를 사용하는 방식이 아닌, 수식으로 해야 시간 내에 통과할 수 있다.

🧐

• 가장 아래 두 개의 코드는 L, R 연산을 deque 자료구조의 rotate()를 이용해서 진행했는데, 시간초과가 발생하여 수식으로 변경했다.