[CLASS 3]백준 9019번 - DSLR

9019번 : DSLR

 

실수로 문제 분류 보기를 눌러버려서 BFS인줄 알고 시작했다...그래서 쉽게 풀었다.

 

근데 코드를 잘 작성하고 제출했는데 계속 시간 초과가 떠서 PyPy3로 제출하니 맞았다. 그 뒤 어떻게 하면 시간 초과를 피할 수 있는지 코드를 확인해 보려고 '맞은 사람'의 Python3 메뉴에 들어가 봤는데..

 

potato좌...

 

파이썬으로 맞은 분이 단 1분 밖에 계시지 않았다.. 이게 어찌된 일인가???? 심지어 20초(제한 시간)에 아슬아슬하게 들어온 것도 아니고 3초컷 하셨다. 어떤 코드인지 정말 궁금하지만 공개를 하지 않으셔서 알 수가 없다. 이런 황당한 경우는 처음 겪는다.

 

내 코드(BFS):

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline
from collections import deque

# DSLR 계산
def dslr(n):
    d1 = n // 1000
    d2 = n // 100 - d1 * 10
    d3 = n // 10 - d2 * 10 - d1 * 100
    d4 = n - d3 * 10 - d2 * 100 - d1 * 1000
    d = (2*n)%10000
    s = n-1 if n else 9999
    l = d2 * 1000 + d3 * 100 + d4 * 10 + d1
    r = d4 * 1000 + d1 * 100 + d2 * 10 + d3

    return [d,s,l,r]

for _ in range(int(input())):
    # 출발점 a, 도착점 b
    a, b = map(int,input().split())

    visited = [False] * 10000

    # 출발점의 dslr을 계산하여 저장
    queue = deque([(dslr(a),'')])
    # 방문 처리
    visited[a] = True

    while queue:
        p = queue.popleft()
        for i,way in enumerate(p[0]):
            if i == 0:
                last = 'D'
            elif i == 1:
                last = 'S'
            elif i == 2:
                last = 'L'
            else:
                last = 'R'
            # 도착점이라면
            if way == b:
                # 이제까지의 경로 출력
                print(p[1]+last)
                queue = False
                break
            elif not visited[way]:
                visited[way] = True
                queue.append((dslr(way),p[1]+last))

 

문제 자체는 BFS로 풀어야 한다는 것만 알게 되었다면 그닥 어렵지 않다. DSLR계산하는 함수를 하나 정의해놓고 BFS를 돌리면서 해당 값에 도달하기 까지의 경로를 저장하면 된다.