[백준] 9019 파이썬 풀이 (in Python)

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

9019번: DSLR

 

제한시간이 6초길래 시간 넉넉한줄 알았는데 시간 초과가 난 문제 ㅋㅋㅋ

from collections import deque

def D(n):
    tmp = n*2
    if tmp > 9999:
        tmp %= 10000
    return tmp

def S(n):
    tmp = n
    if tmp == 0:
        return 9999
    tmp -= 1
    return tmp

def L(n):
    front = n%1000
    back = n//1000
    tmp = front*10 + back
    return tmp

def R(n):
    front = n%10
    back = n//10
    tmp = front*1000+back
    return tmp

def bfs(s, t): # start , target
    queue = deque()
    visited = set() # 우리가 DSLR 연산을 한번 할 때마다 생기는 결과를 저장해둔다.이미 계산된거라면 굳이 할필요 없으니까 절약된다.
    queue.append((s, ""))
    visited.add(s)
    while queue:
        n, op = queue.popleft()
        if n == t:
            print(op)
            return
        tmp = D(n)
        if tmp not in visited:
            visited.add(tmp)
            queue.append((tmp, op+"D"))

        tmp = S(n)
        if tmp not in visited:
            visited.add(tmp)
            queue.append((tmp, op+"S"))

        tmp = L(n)
        if tmp not in visited:
            visited.add(tmp)
            queue.append((tmp, op+"L"))

        tmp = R(n)
        if tmp not in visited:
            visited.add(tmp)
            queue.append((tmp, op+"R"))

for i in range(int(input())):
    start, target = map(int, input().split())
    bfs(start, target)

 

여기서 visited 를 list가 아니라 set으로 만든 이유는 

tmp not in visited 에서 in 연산은 O(n) 이지만 set일 경우 in 연산은 O(1)의 시간복잡도를 가져서 훨씬 시간을 절약한다 

신기해..!!! 

그리고 BFS로 접근을 어떻게 구현하면 좋을지가 어려웠는데, 기본 길찾기 문제처럼 이것도 DSLR이라는 네가지 연산이 존재하는데 길찾기에서는 이게 상하좌우 네 방향이었던 것이다 ... ! 그러므로 똑같이 visited에 방문한 지점을 저장했던 것 처럼, 내가 이미 연산을 해놓은 것이 있으면 굳이 그 연산을 되풀이 하지 않아도 된다 !!! 

복습하자 ~!