백준 9019번 dlsr

bfs로 풀면 될듯하다.

 

근데 쉬프트연산이 좀 번거롭다.

from collections import deque
import sys
t=int(sys.stdin.readline().rstrip())
for _ in range(t):
    a,b=map(int,sys.stdin.readline().rstrip().split())
    q=deque()
    q.append([a,''])
    v=set()
    v.add(a)
    while q:
        cur_num,op=q.popleft()
        if cur_num==b:
            print(op)
            break
        if (cur_num*2)%10000 not in v:
            v.add((cur_num*2)%10000)
            q.append([(cur_num*2)%10000,op+'D'])
        num=cur_num-1
        if num==0:
            num=9999
        if num not in v:
            v.add(num)
            q.append([num,op+'S'])

        l=(cur_num%1000)*10+cur_num//1000
        r=(cur_num%10)*1000+cur_num//10
        
        if l not in v:
            v.add(l)
            q.append([l,op+'L'])
        if r not in v:
            v.add(r)
            q.append([l,op+'R'])

이렇게 작성했다.

복붙하면서 오류가있었다.

from collections import deque
import sys
t=int(sys.stdin.readline().rstrip())
for _ in range(t):
    a,b=map(int,sys.stdin.readline().rstrip().split())
    q=deque()
    q.append([a,''])
    v=set()

    while q:
        cur_num,op=q.popleft()
        if cur_num==b:
            print(op)
            break
        if (cur_num*2)%10000 not in v:
            v.add((cur_num*2)%10000)
            q.append([(cur_num*2)%10000,op+'D'])
        num=cur_num
        if num==0:
            num=9999
        else:
            num-=1
        if num not in v:
            v.add(num)
            q.append([num,op+'S'])

        l=(cur_num%1000)*10+cur_num//1000
        r=(cur_num%10)*1000+cur_num//10
        
        if l not in v:
            v.add(l)
            q.append([l,op+'L'])
        if r not in v:
            v.add(r)
            q.append([r,op+'R'])

pypy로 제출하니 됐다.

이것도 나중에 속도 2배정도 올리는 풀이로 다시 풀어야한다.