[백준] [BFS] 9019. DSLR

9019. DSLR

9019번: DSLR

 

• 고려해야 하는 사항
  • 123을 L하면 1230
  • 5를 R하면 5000이 되어야함
  • → 반드시 4자리 수가 유지되게 해야함

 

 

• 내 풀이 Error 사항
  • 처음에 L,R 돌리는것을 deque.rotate()를 사용하려했으나 deque() 전체를 int로 변환할 방법이 없었다
  • DFS 로 재귀로 돌렸으나 max recursion error 발생
  • result에 D,S,L,R을 넣다빼는 식의 백트래킹 사용했음
    • → 파라미터나, 큐로 넘길때 더해주는 방식으로 하는것이 좋을 것 같다

 

 

• 다른 사람 풀이
  • 모든 사항 고려할 때 bfs로 queue에 담아 돌리기 
  • visited를 list 로 하면 시간초과 → IN 사용해서 확인하는 용도일땐 set 사용해야함
    • list 에서 in 사용: O(N)
    • set에서 in 사용: O(1)
  •  L,R 방향으로 숫자 돌리는 방법
    • L: 1000으로 나눈 몫, 나머지를 구해서 새로운 값으로 연산
    • R: 10으로 나눈 몫, 나머지 구해서 새로운 값으로 연산

#9019

#d: n*2 %10000
#s: n-1 / 0이면 9999
#l: n의 각 자리수를 왼편으로 회전 (deque.rotate(-1))
#r: 각 자리수를 오른편으로 회전

#a를 b로 바꾸는 최소한의 명령어
from collections import deque

def left(n):
    front=n%1000
    back=n//1000
    x=front*10+back
    return x

def right(n):
    front=n//10
    back=n%10
    x=back*1000+front
    return x

def bfs():
    global b
    while queue:
        a, result=queue.popleft()
        if a==b:
            print(*result, sep="")
            return
    
        a2=(a*2)%10000
        if a2 not in visited:
            visited.add(a2)
            queue.append((a2,result+"D"))
    
        if a==0: #a-1==0일때로 하면 a=0인 경우의 D,S,L,R확인 불가
            a2=9999
        else:
            a2=a-1
        if a2 not in visited:
            visited.add(a2)
            queue.append((a2,result+"S"))
   
        a2=left(a)
        if a2 not in visited:
            visited.add(a2)
            queue.append((a2, result+"L"))
  
        a2=right(a)
        if a2 not in visited:
            visited.add(a2)
            queue.append((a2, result+"R"))
      

T=int(input())
for tc in range(T):
    result=""
    queue=deque()
    visited=set() #list in 시간복잡도 O(n), set in 시간복잡도 O(1)
      
    a,b=map(int,input().split())
    queue.append((a,result))
    visited.add(a)
    bfs()