[백준] 9019번 파이썬

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

문제 해결 과정

1. bfs 탐색을 활용하는 문제다. 각 dslr 연산을 노드라고 생각하고 트리의 각 노드에서 dslr연산을 수행해 답을 찾는 과정을 반복하면 된다.

2. 여기서 핵심은 L과 R 연산이다. L 연산의 경우 10을 곱해주고 추후 연산을 진행해 원래 값이 소실되지 않지만 R 연산의 경우 10으로 나누기 때문에 그렇지 않다. 그 부분만 주의해서 코드를 구현하면 다음과 같다.

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

T = int(input())
for _ in range(T):
    A, B = map(int, input().split())
    queue = deque([[A, ""]])
    visited = [False] * 10000
    visited[A] = True

    while queue:
        number, oper = queue.popleft()

        if number == B:
            print(oper)
            break

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

        # S 연산
        oper_result = (number - 1) % 10000
        if not visited[oper_result]:
            visited[oper_result] = True
            queue.append([oper_result, oper + 'S'])

        # L 연산
        temp = 10 * number
        oper_result = temp % 10000 + temp // 10000
        if not visited[oper_result]:
            visited[oper_result] = True
            queue.append([oper_result, oper + 'L'])

        # R 연산
        oper_result = (number % 10 * 1000) + (number // 10)
        if not visited[oper_result]:
            visited[oper_result] = True
            queue.append([oper_result, oper + 'R'])