[BOJ 9019] DSLR (Python3)

www.acmicpc.net/problem/9019

9019번: DSLR

 

from collections import deque
 
def D(n):
    if n*2>9999:
        return (n*2)%10000
    return n*2
 
def S(n):
    if n==0:
        return 9999
    return n-1
 
def L(n):
    d1=n//1000
    d2=(n%1000)//100
    d3=((n%1000)%100)//10
    d4=(((n%1000)%100)%10)
    return ((d2*10+d3)*10+d4)*10+d1
 
def R(n):
    d1=n//1000
    d2=(n%1000)//100
    d3=((n%1000)%100)//10
    d4=(((n%1000)%100)%10)
    return ((d4*10+d1)*10+d2)*10+d3
 
T=int(input())
array=[]
DSLR=["D","S","L","R"]
for _ in range(T):
    array.append(list(map(int, input().split())))
 
def bfs(start, target):
    queue=deque([start])
    traces[start]="0"
    while queue:
        x=queue.popleft()
        if x==target:
            return traces[x][1:]
        i=-1
        for nx in (D(x), S(x), L(x), R(x)):
            i+=1
            if traces[nx]!="":
                continue
            traces[nx]=traces[x]+DSLR[i]
            queue.append(nx)
 
for i in range(T):
    traces=[""]*10000
    print(bfs(array[i][0], array[i][1]))
 

BFS 문제이다. (BFS, DFS 문제만 푸는듯..딴 분야도 열심히 풀어야겠다)

스타트링크(BOJ 5014번)와 유사한 문제이다.

 

0부터 9999까지 숫자 배열을 만든 다음에 기록들을 저장한다.

각 점에서에서 D,S,L,R로 BFS 탐색 한 후, traces를 기록 후 큐에 넣어준다(이때 방문한 숫자는 탐색하지 않음).

queue에서 target 숫자가 나오면, traces[target]을 리턴한다. 이렇게 하면 최소한의 명령어 나열을 알 수 있다.

코드가 Little bit 더러운 느낌쓰.

 

다른 분들 코드 보니까 큐에 (DSLR 연산 한 숫자, way) 를 집어넣어 이 아이템을 pop 했을 때 해당 way에+수행한 연산을 덧붙이는 방식을 취했다. 이게 가독성이 더 좋고 간편한듯. 방문한 노드는 visited 배열을 통해 체크한다.