[BOJ] 9019 / DSLR / Python 파이썬

[BOJ] 9019 / DSLR / Python 파이썬

[BOJ] 9019 / DSLR / Python 파이썬

https://www.acmicpc.net/problem/9019

9019번: DSLR

 

풀이

전형적인 Queue 를 사용한 BFS 문제라고 생각하였다가 시간초과로 꽤나 고생을 하였다.

 

풀고나니 파이썬으로는 해결이 불가능 하다고 결론을 내었지만 그래도 배울것이 많은 문제였다.

 

1. List 로 visted 를 만드는 것보다, set 이 더 빠르다.
   • List 에서 in 을 사용하는 탐색은 O(n) -> list 의 index 로 탐색하여야 유리하다.
   • Set 에서 in 을 사용하는 탐색은 O(1)
2. 숫자의 자리수를 변경 할때, 수식을 이용하자
   • 문자열로 처리한후 다시 int 바꾸는것이 생각보다 시간을 잡아 먹는다.

 

deque 를 이용하여 구현하였지만, 시간초과가 나시는 분들은 python 아닌 Pypy3 로 체점해 보시길...

from collections import deque

case = int(input())

for _ in range(case):
    A, B = map(int, input().split())
    visited = set()
    queue = deque()
    queue.append((A, ""))

    while True:
        Q, command = queue.popleft()

        if Q == B:
            print(command)
            break

        doubleQ = (Q*2) % 10000
        if doubleQ not in visited:
            visited.add(doubleQ)
            queue.append((doubleQ, command + "D"))

        mQ = Q-1 if Q != 0 else 9999
        if mQ not in visited:
            visited.add(mQ)
            queue.append((mQ, command + "S"))

        LQ = (Q % 1000) * 10 + (Q//1000)
        if LQ not in visited:
            visited.add(LQ)
            queue.append((LQ, command + "L"))

        RQ = (Q % 10) * 1000 + (Q//10)
        if RQ not in visited:
            visited.add(RQ)
            queue.append((RQ, command + "R"))

 

 

---

참고 블로그

https://paris-in-the-rain.tistory.com/94

[BOJ 백준] 9019번 : DSLR (Python, 파이썬)