백준 9019번: DSLR (Python, PyPy3)

접근

문제 접근 및 풀이까지는 쉬웠는데 시간 초과 때문에 아주 오래 시간을 잡아먹었으나, 생각지 못했던 곳에서 해결된 문제였다. 시간 문제로 인해 PyPy3으로 해결하였다.

문제에 접근 자체는 매우 간단한 BFS 알고리즘 문제였다. 주어진 수에 D, S, L, R 연산을 각각 하고, 이를 queue에 추가한다. 동시에 길이가 10,000인 dp 리스트를 작성하여 해당 수까지의 경로를 저장한다.

이 이해하기도 쉬운 해결 방법을 시간 안에 들어가기 위하여 애를 많이 썼다. 끙끙 앓으면서 시간이 들어갈 만한 부분을 지워나가기도 했지만 마지막 해결 방법은 queue 순환 부분을 bfs 함수로 만든 것이다. 예전 문제에서도 한번 이렇게 간신히 시간안에 들었던 기억이 난다. 지역 변수를 읽는 것이 전역 변수를 읽는 것보다 빠르기 때문에 일어나는 현상이다.

코드

import sys


def dslr(x):
    d1 = x // 1000
    d2 = x % 1000 // 100
    d3 = x % 100 // 10
    d4 = x % 10
    d = 2 * x % 10000
    s = x - 1 if x else 9999
    l = d2 * 1000 + d3 * 100 + d4 * 10 + d1
    r = d4 * 1000 + d1 * 100 + d2 * 10 + d3
    return [d, s, l, r]


def bfs():  # queue 순환 부분을 함수로 만들면 시간이 단축된다..
    q = [a]
    while dp[b] == '':
        now = q.pop(0)
        nowLetter = dp[now]
        next = dslr(now)
        nextLetter = ['D', 'S', 'L', 'R']
        for i, n in enumerate(next):
            if dp[n] == '':
                dp[n] = nowLetter + nextLetter[i]
                q.append(n)
    return dp[b]


for _ in range(int(sys.stdin.readline())):
    a, b = map(int, sys.stdin.readline().split())
    dp = [''] * 10000
    print(bfs())

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!