수리링의 데이터교실

from collections import deque

디큐는 속도가 빠른 리스트로 생각해도 좋다.

코딩 테스트에서 파이썬으로 Queue, BFS, FIFO 방식의 알고리즘 접근이 필요할 때 리스트를 디큐로 바꾸어주면 속도 이슈 해결이 가능하다.

a_list = [1, 2, 3, 4, 5]
# [1, 2, 3, 4, 5]

a_dq = deque(a_list)
# deque([1, 2, 3, 4, 5])

이렇게 간단하게 디큐 함수로 바꾸어주기만 하면 된다.

a_dq.pop()
a_dq.popright()
# 5

a_dq.popleft()
# 1

a_dq
# deque([2, 3, 4])

a_dq.append(1004)
# deque([2, 3, 4, 1004])

• 디큐 맨 마지막 값을 뺄 때 : .pop()
• 디큐 맨 처음 값을 뺄 때 : .popleft()
  • 주의 / .pop(0)과 같이 사용하면 에러 발생!
• pop과 popleft 모두 기존의 디큐를 수정, 업데이트하는 파괴적 함수!
• 디큐 맨 뒤에 값을 추가할 때 : .append()

디큐를 활용한 bfs

graph_list = [
    [],
    [2,3,8], 
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]


def bfs(graph, start):
    need_visit = deque([])
    visited    = deque([])
    need_visit.append( start )
    while need_visit:
        node = need_visit.popleft()
        if node not in visited:
            visited.append(node)
            temp = graph[node]
            temp_reverse = list(reversed(temp))
            need_visit.extend( temp_reverse )
    return visited
    
    
  bfs(graph_list, 1)
  # deque([1, 8, 3, 2, 7, 5, 4, 6])