[Baekjoon] - 9019. DSLR (G4)

1. Problem 📃
📚 ソース-9019 - DSLR
問題の説明
4つの命令D,S,L,Rを用いた単純な計算機がある.この計算機には0または10000未満の10進数を格納できるレジスタがあります.各コマンドは、このレジスタに格納されているnを次のように変換します.nの4桁をd 1,d 2,d 3,d 4(すなわちn=(d 1)と呼ぶ× 10 + d2) × 10 + d3) × 10+d4)

D:Dはnを2倍にする.結果値が9999より大きい場合は、10000を取得します.その結果、レジスタに値(2 nmod 10000)が保存されます.

S:Sはnから1を減算し、n−1をレジスタに格納する.nが0の場合、9999はレジスタに格納される.

L:Lはnの各ビット数を左に回転させ、結果をレジスタに格納する.この演算が完了すると、レジスタに格納された4桁は左側からd 2、d 3、d 4、d 1に変化する.

R:Rはnの各ビット数を右に回転させ、結果をレジスタに格納する.この演算が完了すると、レジスタに格納された4桁が左側からd 4,d 1,d 2,d 3に変化する.

前述したように、LおよびRコマンドは、10進数と仮定して演算を実行する.例えば、n=1234の場合、ここではLが2341になり、Rが4123になる.
作成するプログラムは、与えられた2つの異なる整数AとB(A≠B)に対して、AをBに変換する最小命令を生成するプログラムです.たとえば、A=1234、B=3412の場合、次の2つのコマンドを使用してAをBに変換できます.
1234 →L 2341 →L 3412
1234 →R 4123 →R 3412
したがって、この場合、プログラムはLLまたはRRを出力する必要があります.
注意nビット数で0を含む場合.例えば、Lが1000に適用されると0001となり、結果は1となる.ただし、Rが適用される場合は0100となり、結果は100となる.
入力
プログラム入力はT個のテスト用例からなる.試験用例個数Tは、入力の第1行が付与される.各試験例には、2つの整数AおよびB(A≠B)がスペースで区切られ、Aはレジスタの初期値を表し、Bは最終値を表す.AとBはいずれも0または10000未満である.
しゅつりょく
AからBへの変換に必要な最小コマンド列を出力します.可能なコマンドリストが複数ある場合は、いずれかを出力します.
I/O例
入力例出力312343210000116 LLLDDDD
2. Logic 👨‍🏫
以下のロジックは、BFSアルゴリズムを使用して値を検出したときに出力されるロジックです.
LogicBFS 준비물: deque, visited(방문 확인)1.最初に与えられた数値と空の文字列をqueueに挿入し、開始します.
2.D、S、L、Rに基づいて条件を設定する
- D 👉 * 2を数値とし、10000を余数とする(9999より大きい場合は10000)           )
- S 👉 -1を数値とし、10000を剰余とする(nが0の場合は9999が格納される)           条件があるから=>-1 % 10000를 하게 되면 9999 출력)
- L 👉 一番左の数字を一番右に移動する必要があるので、次のコードに従って書きます.
            (num % 1000) * 10 + num//1000)- R 👉 一番右の数字を一番左に移動する必要があるので、次のコードに従って書きます.
            ((num % 10) * 1000 + num//10)3.それぞれDSLRの条件でアクセスしていなければ、アクセスすると同時に、
    挿入queue4.숫자와 각각 해당되는 문자を繰り返し使用し、必要な数字と一致した場合の文字列出力
3. Code 💻
1.私が解いたパスワード😁

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

def bfs(before, after):
    queue = deque()
    queue.append((before, ""))
    visited = [0] * 10000
    visited[before] = 1

    while queue:
        num, word = queue.popleft()
        if num == after:
            return word
        
        # D
        if not visited[(num * 2) % 10000]:
            queue.append(((num*2)%10000, word + "D"))
            visited[(num * 2) % 10000] = 1

        # S
        if not visited[(num - 1) % 10000]:
            queue.append(((num-1)%10000, word + "S"))
            visited[(num - 1) % 10000] = 1
        
        # L
        if not visited[((num % 1000) * 10 + num//1000)]:
            queue.append((((num % 1000) * 10 + num//1000), word + "L"))
            visited[((num % 1000) * 10 + num//1000)] = 1

        # R
        if not visited[((num % 10) * 1000 + num//10)]:
            queue.append((((num % 10) * 1000) + num // 10, word + "R"))
            visited[((num % 10) * 1000) + num // 10] = 1

T = int(input())

for i in range(T):
    before, after = map(int, input().split())
    print(bfs(before, after))