Perfluorodecalin

자료구조(큐, 힙, BFS, DFS) 치트시트

2 min read

Queue (BFS)

from collections import deque
 
q = deque()
q.append(start)
while q:
    cur = q.popleft()

Priority Queue (최소힙)

import heapq
 
hq = []
heapq.heappush(hq, (priority, value))
x = heapq.heappop(hq)

(priority, value) 형태로 우선순위 주기

실전 코테에서 가장 많이 쓰는 형태.

import heapq  
hq = [] 
heapq.heappush(hq, (priority, data))   
priority, data = heapq.heappop(hq)
  • priority가 작을수록 먼저 나온다
  • 여러 기준이 있으면 튜플로 확장하면 됨
    예:
import heapq
heapq.heappush(hq, (time, request_time, job_id))

여러 우선순위를 튜플로 처리 (자동 정렬)

파이썬에서는 튜플을 비교하면 앞 요소부터 차례로 비교한다.

import heapq
 
hq = []
for idx, (start, duration) in enumerate(jobs):
    heapq.heappush(hq, (duration, start, idx))
# (1순위: 소요시간, 2순위: 요청시간, 3순위: 작업번호)

이렇게 하면 별도 compare 함수 없이도 다양한 우선순위 표현 가능.

최대힙(Max-Heap)처럼 사용하기

heapq는 최소힙이므로 음수(-) 를 붙여서 넣는다.

import heapq  
hq = [] 
heapq.heappush(hq, (-value, value)) 
max_value = heapq.heappop(hq)[1]

이미 정렬된 리스트를 힙으로 변환

heapq.heapify(arr)

가장 작은 N개 / 가장 큰 N개 요소 추출

import heapq  smallest = heapq.nsmallest(3, arr) largest = heapq.nlargest(3, arr)

DFS (재귀)

def dfs(x):
    visited[x] = True
    for nxt in graph[x]:
        if not visited[nxt]:
            dfs(nxt)

BFS

def bfs(start):
    q = deque([start])
    visited[start] = True
    while q:
        cur = q.popleft()
        for nxt in graph[cur]:
            if not visited[nxt]:
                visited[nxt] = True
                q.append(nxt)

그래프 인접 리스트 생성

graph = [[] for _ in range(n + 1)]
for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)

그래프 뷰