1. 문제 설명

DSLR

2. 문제 분석

현재 노드에서 변형 가능한 식이 주어지고, 범위 안에 있고 방문한 적이 없을 때 방문해가면서 최소한의 방문 횟수를 카운트하는 문제. 이 문제는 특히 이 조건식을 어떻게 사용했는지를 기록해야 하기 때문에 큐에 따로 path를 함께 전달하거나 백트래킹을 사용해야 한다.

3. 나의 풀이

import sys
from collections import deque

t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    num1, num2 = map(int, sys.stdin.readline().rstrip().split())
    queue = deque()
    visited = [False for _ in range(10000)]
    cmd = ''
    queue.append([num1, cmd])
    visited[num1] = True

    while queue:
        cur_node, cmd = queue.popleft()
        if cur_node == num2: break

        # D 연산
        next_node = (cur_node*2)%10000
        if not visited[next_node]:
            visited[next_node] = True
            queue.append([next_node, cmd + 'D'])

        # S 연산
        if cur_node == 0: next_node = 9999
        else: next_node = cur_node - 1

        if not visited[next_node]:
            visited[next_node] = True
            queue.append([next_node, cmd + 'S'])

        # L 연산
        next_node = (cur_node % 1000) * 10 + cur_node // 1000
        # 4개 숫자 있을 때 d1을 따로 구하고, d2 d3 d4와 합하자.

        if not visited[next_node]:
            visited[next_node] = True
            queue.append([next_node, cmd + 'L'])
        # R 연산
        next_node = (cur_node % 10) * 1000 + cur_node // 10
        # 4개 숫자 있을 때 d4를 따로 구하고 d1 d2 d3 앞에 둔다.

        if not visited[next_node]:
            visited[next_node] = True
            queue.append([next_node, cmd + 'R'])
    print(cmd)