[Python] deque 자료구조

 

덱(deque)는 스택(Stack)과 큐(Queue)의 기능을 모두 가지고 있는 자료 구조이다.

즉, 양 끝에서 삽입/삭제가 모두 가능한 자료구조로, 스택과 큐보다는 유연하고 링크드리스트보다는 덜 유연한 자료 구조라고 한다.

덱(deque)을 활용하기 위해서는, Collection 모듈이 필요하다. BFS를 구현하는 데 유용하게 활용할 수 있겠다.

Collections: list, tuple, set, dict 등 내당 컨테이너에 대한 대안을 제공하는 Python Built-In 확장 모듈

from collections import duque
from collections import OrderedDict
from collections import defaultdict
from collections import Counter
from collections import namedtuple

 

deque 주요 메소드

• append(x) : deque의 오른쪽 끝에 항목 x 추가
• appendleft(x) : deque의 왼쪽 끝에 항목 x 추가
• pop() : deque의 오른쪽 끝에서 항목을 제거하고 반환
• popleft() : deque의 왼쪽 끝에서 항목을 제거하고 반환
• extend(iterable) : iterable의 모든 항목을 deque의 오른쪽 끝에 추가
• extendleft(iterable) : iterable의 모든 항목을 deque의 왼쪽 끝에 추가
• rotate(n) : deque를 n번 만큼 회전. 양수면 오른쪽 방향, 음수면 왼쪽 방향으로 회전
• clear() : deque의 모든 항목을 제거
• count(x) : deque에서 x가 등장하는 횟수를 반환
• index(x[, start[, end]]) : deque에서 x가 처음 등장하는 위치를 반환. (start와 end 인덱스 선택적으로 지정 가능)
• remove(value) : deque에서 첫 번째로 등장하는 value를 제거. (value가 없으면 ValueError 발생)
• reverse() : deque의 항목들을 역순으로 정렬

 

예제

문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

해결

n, m, s = map(int, input().split())
li = [[] for _ in range(n + 1)]

# 인접 리스트 생성
for _ in range(m):
    a, b = map(int, input().split())
    li[a].append(b)
    li[b].append(a) 

# 각 리스트의 원소(정점)을 오름차순으로 정렬
for i in li:
    i.sort()

# 방문 처리 리스트 생성
visit = [False] * (n + 1)
stack = [s]
dfs = []
bfs = []

# DFS 스택 생성
while stack:
    node = stack.pop() # 방문 노드 처리
    if not visit[node]:
        visit[node] = True
        # 해당 노드에 연결된 노드의 리스트를 역순으로 순회하며 스택에 쌓음
        # 스택처리 시 큰 노드를 먼저 쌓고 작은 노드를 먼저 꺼내기 위함
        for i in reversed(li[node]):
            stack.append(i)
        dfs.append(node)

from collections import deque # deque 자료구조 처리를 위해 import
visit = [False] * (n + 1)
Q = deque([s])

# BFS 큐 생성(deque 사용)
while Q:
    node = Q.popleft() # 방문 노드 처리(큐로 처리하기 위해 왼쪽에서부터 꺼냄)
    if not visit[node]:
        visit[node] = True
        for i in (li[node]):
            Q.append(i)
        bfs.append(node)

for i in dfs:
    print(i, end = ' ')
print()
for i in bfs:
    print(i, end = ' ')

 

    BFS 처리를 위한 큐를 생성하는 과정에서 deque를 활용하였다.