[ 백준 9019 ] DSLR - Python

문제 보기

이 문제는 BFS 문제이다. (+ 시간 초과)

 

백준 문제를 풀면서 시간제한이 6초인 문제는 처음 봤다. 하지만 6초라는 시간도 짧았다. 이 문제는 BFS를 구현하는 것보다 시간을 단축시키는 아이디어가 더 중요하였다.

 

•  문제 접근
  • 입력받는 A 값을 큐에 삽입한다.
  • A를 이용해서 D, S, L, R 과정을 수행해보고 가능한 경우는 결괏값을 큐에 삽입한다.
  • 목푯값을 만날 때까지 위 과정을 진행한다.

D와 S과정은 시간 초과와 별 상관없어 보였지만 L, R은 어떻게 수행하냐에 따라서 시간과 밀접한 연관이 있을 것이라고 생각했다. 제일 먼저 문자열 연산으로 접근하였지만 시간 초과가 발생하였다. 결국 수식을 활용해서 구하는 해답을 찾아내었으며 통과하였다.

 

• 알고리즘
  • 입력받은 A 값을 큐에 삽입한다.
  • 큐의 제일 왼쪽 값을 pop 한 후 D, S, L, R 과정을 수행한다.
    - L은 값 % 1000 * 10 + 값 // 1000 방법으로 수행한다.
    - R은 값 % 10 * 1000 + 값 // 10 방법으로 수행한다.
  • B값을 만날 때까지 진행한다.

코드

from collections import deque


def bfs(start, end):
    q = deque([[start, ""]])
    visited = [0] * 10000
    visited[start] = True

    while q:
        num, operation = q.popleft()

        if num == end:
            return operation

        # D
        if not visited[num * 2 % 10000]:
            visited[num * 2 % 10000] = True
            q.append([num * 2 % 10000, operation + "D"])
        # S
        if not visited[(num - 1) % 10000]:
            visited[(num - 1) % 10000] = True
            q.append([(num - 1) % 10000, operation + "S"])
        # L
        if not visited[num % 1000 * 10 + num // 1000]:
            visited[num % 1000 * 10 + num // 1000] = True
            q.append([num % 1000 * 10 + num // 1000, operation + "L"])
        # R
        if not visited[num % 10 * 1000 + num // 10]:
            visited[num % 10 * 1000 + num // 10] = True
            q.append([num % 10 * 1000 + num // 10, operation + "R"])


if __name__ == "__main__":

    # input
    T = int(input())
    for _ in range(T):
        A, B = map(int, input().split())
        print(bfs(A, B))