[백준] 9019 - DSLR

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

9019번: DSLR

문제 한줄 이해

-D S L R의 각 명령어를 수행해 A 숫자가 B가 되기 위해 필요한 최소한의 명령어 구하기

 

생각난 풀이

1번째 방법: 각각의 명령어를 수행해 큐에 담아서 탐색하는 BFS가 떠올랐고 이미 방문한 숫자에 대해 다시 탐색하지 않게 visited처리를 해주었다. 이때 123에 R명령어를 수행하면 312가 되는것이 아니고 3012가 되는 점을 유의하기!

import sys
from collections import deque
t = int(sys.stdin.readline())

for i in range(t):
    visited = [False] * 10000
    a, b = map(int,sys.stdin.readline().split())
    
    que = deque()
    que.append((a,""))
    visited[a] = True
    while que:
        nowx, nowc = que.popleft()
        if nowx == b:
            print(nowc)
            break
        for k in ("D","S","L","R"):
            if k == "D":
                nextn = nowx*2 % 10000
                if visited[nextn] == False:
                    visited[nextn] = True
                    que.append((nextn,nowc+"D"))
            if k == "S":
                if nowx == 0:
                    nextn = 9999
                else:
                    nextn = nowx-1
                if visited[nextn] == False:
                    visited[nextn] = True
                    
                    que.append((nextn,nowc+"S"))
            if k == "L":
                nextn = nowx // 1000 + (nowx % 1000)*10
                if visited[nextn] == False:
                    visited[nextn] = True
                    que.append((nextn,nowc+"L"))
            if k == "R":
                nextn = nowx // 10 + (nowx % 10) * 1000
                if visited[nextn] == False:
                    visited[nextn] = True
                    que.append((nextn,nowc+"R"))