📚 9019 - DSLR

DSLR

이해

너비 우선 탐색으로 모든 노드를 방문하다가 b를 찾았다면, 종료하면 된다.

(1) D : n은 2배로 나눈다. (10,000보다 큰 경우, 10000으로 나눈 나머지) → 현재숫자 * 2 % 10000
(2) S : n에서 1을 뺀다. (0인 경우, 9999로) → (현재숫자-1) % 10000
(3) L : n의 각 자릿수를 왼편으로 회전 (d1d2d3d4 -> d2d3d4d1) → ((현재 숫자 // 1000) + (현재 숫자 % 1000) * 10) % 10000
(4) R : n의 각 자릿수를 오른편으로 회전 → ((현재숫자 % 10) * 1000 + (현재숫자 // 10) % 10000)

소스

import sys
from collections import deque

read = sys.stdin.readline

t = int(read())


def bfs():
    q = deque()
    q.append((a, ''))
    visited = [False] * 10000

    while q:
        next_data, path = q.popleft()

        if next_data == b:
            print(path)
            break

        num = (next_data * 2) % 10000
        if not visited[num]:
            visited[num] = True
            q.append((num, path + 'D'))

        num = (next_data - 1) % 10000
        if not visited[num]:
            visited[num] = True
            q.append((num, path + 'S'))

        num = (next_data // 1000 + (next_data % 1000) * 10) % 10000
        if not visited[num]:
            visited[num] = True
            q.append((num, path + 'L'))

        num = ((next_data % 10) * 1000 + next_data // 10) % 10000
        if not visited[num]:
            visited[num] = True
            q.append((num, path + 'R'))


while t > 0:
    a, b = map(int, read().split())

    bfs()

    t -= 1

채점 결과