Ch.12 BFS, DFS, 그리고 DAG¶
< 사례 - 카테고리 트리를 매번 재귀로 조회한다 | 유사 사례와 키워드 정리 >
앞에서 트리 순회를 재귀에서 반복문으로 바꾸는 방법을 봤다. 그런데 반복문 순회에도 두 가지 방식이 있다: BFS와 DFS. 어떤 방식을 쓰느냐에 따라 결과 순서, 메모리 사용, 알고리즘이 풀 수 있는 문제의 종류가 전부 달라진다.
반복문 순회, 어느 방향부터 도나 - 너비 우선(BFS)¶
재귀를 걷어냈으니 이제 순회 순서를 직접 정해야 한다. 가까운 것부터 펼치는 쪽을 먼저 본다. "같은 레벨의 노드를 먼저 방문"하는 방식이다. Queue(FIFO)를 사용한다.
from collections import deque
def bfs(start, children_map):
visited = []
queue = deque([start])
while queue:
node = queue.popleft() # FIFO: 먼저 넣은 것부터
visited.append(node)
for child in children_map.get(node, []):
queue.append(child)
return visited
list.pop(0) vs deque.popleft() - 왜 deque인가¶
list.pop(0)을 쓰면 안 되는 이유는 단순하다. O(n)이기 때문이다.
graph LR
subgraph "list.pop(0) - O(n)"
L1["[A, B, C, D, E]"] -->|"pop(0)"| L2["[B, C, D, E]"]
L2 -->|"내부 동작"| L3["뒤의 4개를 한 칸씩 앞으로 복사"]
end리스트는 연속된 메모리에 원소가 일렬로 놓여 있다. 앞에서 빼면 뒤의 모든 원소를 한 칸씩 당겨야 한다. n개 있으면 n번의 복사가 일어난다.
collections.deque는 양쪽 끝에서 O(1) 삽입/제거가 가능한 이중 연결 리스트 기반의 자료구조다.
| 연산 | list | deque |
|---|---|---|
| 뒤에서 추가 (append) | O(1) 평균 | O(1) |
| 뒤에서 제거 (pop) | O(1) | O(1) |
| 앞에서 추가 (insert(0)/appendleft) | O(n) | O(1) |
| 앞에서 제거 (pop(0)/popleft) | O(n) | O(1) |
| 인덱스 접근 (a[i]) | O(1) | O(n) |
BFS처럼 앞에서 빼고 뒤에 넣는 패턴(FIFO)에는 deque가 정답이다. Ch.10에서 본 "자료구조 선택이 성능을 결정한다"가 여기서도 그대로 적용된다.
(deque는 인덱스 접근은 느리다. 중간 원소를 자주 읽어야 하면 list가 낫다. 자료구조는 항상 "어떤 연산을 자주 하는가"로 골라야 한다.)
너비가 아니라 깊이로 파고든다면 - 깊이 우선(DFS)¶
같은 노드를 다 도는 또 하나의 방향은 형제를 미뤄두고 끝까지 내려가는 쪽이다. "한 방향으로 끝까지 파고들고, 막히면 돌아오는" 방식이다. Stack(LIFO)을 사용한다.
def dfs_iterative(start, children_map):
visited = []
stack = [start]
while stack:
node = stack.pop() # LIFO: 마지막에 넣은 것부터
visited.append(node)
for child in reversed(children_map.get(node, [])):
stack.append(child)
return visited
reversed()를 쓰는 이유는, 자식을 왼쪽부터 방문하고 싶기 때문이다. Stack은 LIFO니까 마지막에 넣은 게 먼저 나온다. 왼쪽 자식을 먼저 방문하려면 오른쪽부터 push해야 한다.
재귀 DFS vs 명시적 Stack DFS¶
코드는 재귀가 더 간결하다. 트리 구조와 코드가 그대로 닮는다.
def dfs_recursive(node, children_map, visited):
visited.append(node)
for child in children_map.get(node, []):
dfs_recursive(child, children_map, visited)
그런데 깊이가 깊어지면 함정이 있다.
import sys
# 깊이 1만의 일자형 트리 (linked list 같은 형태)
children_map = {i: [i + 1] for i in range(10_000)}
dfs_recursive(0, children_map, [])
# RecursionError: maximum recursion depth exceeded
Python 기본 재귀 제한 1,000에 걸린다. sys.setrecursionlimit(20_000)으로 늘려도 OS Stack이 한계라서 결국 SegFault로 죽을 수 있다 (Ch.4에서 봤다).
명시적 Stack 버전은 Heap 메모리의 list를 쓰니까 OS Stack에 영향이 없다. 깊이 100만도 문제없다.
"트리 깊이가 사용자 데이터에 따라 달라진다"면 명시적 Stack이 답이다. 카테고리, 댓글, 조직도, 파일 시스템 전부 그렇다.
BFS (Breadth-First Search, 너비 우선 탐색)
같은 깊이의 노드를 먼저 방문하는 탐색 방식이다. Queue(FIFO)를 사용한다. "최단 경로 찾기"에 적합하다. 레벨 단위로 처리해야 하는 경우(조직도의 같은 직급, 카테고리의 같은 깊이)에 쓴다. Queue에 같은 레벨의 모든 노드가 들어가므로 트리가 넓으면 메모리 사용이 크다.
DFS (Depth-First Search, 깊이 우선 탐색)
한 방향으로 끝까지 파고든 뒤 돌아오는 탐색 방식이다. Stack(LIFO)이나 재귀를 사용한다. "모든 경로 탐색"이나 "존재 여부 확인"에 적합하다. 한 경로의 깊이만큼만 메모리를 쓰므로 BFS보다 메모리 사용이 적다. 재귀 구현은 깔끔하지만 깊은 트리에서 Stack Overflow 위험이 있다.
그래서 둘 중 뭘 고르나 - 갈리는 건 메모리¶
방향 두 개를 다 봤으니, 카테고리 트리에서 어느 쪽을 집을지 따져야 한다. 두 알고리즘 모두 "모든 노드를 한 번씩 방문"하는 면에서 시간 복잡도는 동일하다.
| 항목 | BFS | DFS |
|---|---|---|
| 시간 복잡도 | O(V + E) | O(V + E) |
| 공간 복잡도 (최악) | O(W) - W: 최대 너비 | O(H) - H: 최대 깊이 |
| 자료구조 | Queue (deque) | Stack (list) 또는 재귀 |
| 메모리 패턴 | 넓은 트리에서 큼 | 깊은 트리에서 큼 |
| 적합 문제 | 최단 경로, 레벨 처리 | 경로 탐색, 사이클 감지 |
V는 노드 수(Vertex), E는 간선 수(Edge)다.
차이는 메모리에서 나온다. 트리 모양에 따라 어느 게 메모리를 더 쓰는지가 갈린다.
- 균형 잡힌 이진 트리에서 노드가 백만 개라면, 최대 너비는 50만, 최대 깊이는 약 20이다. BFS는 50만, DFS는 20을 메모리에 들고 있어야 한다. DFS가 압도적으로 유리하다.
- 일자형 트리(linked list 모양)에서는 BFS도 DFS도 메모리 사용이 비슷하다.
- 넓고 얕은 트리(부모-자식 1대 1000 같은 구조)에서는 DFS도 메모리 부담이 있다.
"최단 경로가 필요한가, 경로 자체를 찾고 싶은가"로 갈리고, 거기서 메모리를 따져 정한다.
그럼 어떤 상황에 BFS, 어떤 상황에 DFS?¶
메모리만으로는 답이 안 나오고, 풀려는 문제의 모양까지 봐야 결정이 떨어진다.
| 상황 | 추천 | 이유 |
|---|---|---|
| 최단 경로 찾기 | BFS | 가까운 것부터 탐색하니까 처음 찾은 게 최단 |
| 모든 경로 탐색 | DFS | 끝까지 가봐야 알 수 있음 |
| 레벨 단위 처리 | BFS | 같은 깊이의 노드를 한꺼번에 |
| 깊이가 매우 깊은 경우 | DFS (반복문) | BFS는 Queue에 모든 형제를 담아야 함 |
| 트리가 매우 넓은 경우 | DFS | 깊이가 얕으니까 메모리 적게 씀 |
| 사이클 감지 | DFS | 방문 중인 노드를 다시 만나면 사이클 |
| 위상 정렬 | BFS (Kahn) 또는 DFS | 둘 다 가능 |
트리를 넘어 일반 그래프로 가면 무엇부터 정해야 하나¶
카테고리는 트리였지만 실무 의존 관계는 트리가 아니다. 일반 그래프로 한 단계 일반화하는데, 트리와 달리 표현 방식부터 골라야 한다.
인접 리스트 (Adjacency List)¶
각 노드마다 "이 노드와 연결된 노드들의 리스트"를 들고 있다. Dict로 표현하는 게 가장 흔하다.
인접 행렬 (Adjacency Matrix)¶
V x V 크기의 2차원 배열에 matrix[i][j] = 1이면 i에서 j로 가는 간선이 있다는 뜻이다.
# A=0, B=1, C=2, D=3, E=4
matrix = [
[0, 1, 1, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
]
둘의 트레이드오프¶
| 항목 | 인접 리스트 | 인접 행렬 |
|---|---|---|
| 공간 복잡도 | O(V + E) | O(V²) |
| 간선 존재 확인 | O(degree) | O(1) |
| 모든 이웃 순회 | O(degree) | O(V) |
| 간선 추가/삭제 | O(1) (리스트 append) | O(1) |
| 적합한 그래프 | 희소 그래프 (간선이 적음) | 밀집 그래프 (간선이 많음) |
실무 그래프는 대부분 희소하다. SNS 친구 관계, 페이지 링크, 패키지 의존성 모두 노드 수 대비 간선이 훨씬 적다. 인접 리스트가 기본 선택이고, 인접 행렬은 노드 수가 작거나(< 1000) 거의 모든 노드가 서로 연결된 경우에만 쓴다.
(NetworkX, igraph 같은 그래프 라이브러리는 내부적으로 인접 리스트를 쓴다. 행렬 연산이 필요할 때만 변환한다.)
트리와 달리 그래프엔 사이클이 생긴다 - 어떻게 잡나¶
트리에는 없던 위험이 일반 그래프에서 새로 생긴다. 자기 자신으로 돌아오는 길이다. 그래프에서 사이클(순환)이 있는지 확인하는 건 실무에서 자주 필요하다. 빌드 시스템에서 모듈 A가 B에 의존하고 B가 다시 A에 의존하면 빌드가 불가능하다. 이걸 사전에 잡아야 한다.
DFS로 사이클을 탐지하는 표준 방법은 노드에 세 가지 상태를 두는 거다.
WHITE, GRAY, BLACK = 0, 1, 2 # 미방문, 방문 중, 완료
def has_cycle(graph):
color = {node: WHITE for node in graph}
def dfs(node):
color[node] = GRAY # 방문 중 표시
for neighbor in graph[node]:
if color[neighbor] == GRAY:
return True # 방문 중인 노드를 다시 만나면 사이클
if color[neighbor] == WHITE and dfs(neighbor):
return True
color[node] = BLACK # 완료 표시
return False
for node in graph:
if color[node] == WHITE:
if dfs(node):
return True
return False
핵심은 GRAY(현재 DFS 경로에 있는 노드)다. DFS 도중에 GRAY 노드를 다시 만나면, 그건 자기 자신으로 돌아온 거니까 사이클이다.
(이 코드도 재귀를 쓰니까 깊은 그래프에서는 명시적 Stack으로 바꿔야 한다. 위에서 본 그대로다.)
사이클이 없도록 보장된 그래프는 뭘 할 수 있나¶
사이클을 잡아내는 데서 그치지 않고, 아예 사이클이 없다고 보장된 그래프가 실무의 주역이다. 실무에서 그래프가 가장 자주 등장하는 형태가 DAG(방향 비순환 그래프)다.
- 방향(Directed): 간선에 방향이 있다 (A → B는 있지만 B → A는 아닐 수 있다)
- 비순환(Acyclic): 사이클이 없다 (A → B → C → A 같은 순환이 없다)
graph LR
A["빌드: utils"] --> B["빌드: api"]
A --> C["빌드: worker"]
B --> D["테스트: integration"]
C --> D
D --> E["배포: staging"]실무에서 DAG를 만나는 곳:
| 사례 | 노드 | 간선 |
|---|---|---|
| 빌드 시스템 (Bazel, Make, Gradle) | 빌드 타겟/모듈 | 의존 관계 |
| CI/CD 파이프라인 (GitHub Actions, Jenkins) | 작업(Job/Stage) | 실행 순서 |
| Airflow DAG | Task | 선후행 관계 |
| Spark 작업 그래프 | RDD/DataFrame 변환 | 종속 관계 (lineage) |
| 패키지 매니저 (pip, npm, cargo) | 패키지 | 의존성 |
| Makefile | 빌드 타겟 | 의존 규칙 |
| Terraform 리소스 그래프 | 인프라 리소스 | 생성 순서 |
| React Hooks 의존성 배열 | 상태값 | useEffect 트리거 관계 |
Airflow를 쓰는 ML 엔지니어라면 매일 DAG를 그린다. Spark의 lazy evaluation도 내부적으로 DAG를 만들고, 마지막 action 시점에 한꺼번에 최적화해서 실행한다.
DAG (Directed Acyclic Graph, 방향 비순환 그래프)
간선에 방향이 있고 사이클이 없는 그래프다. 의존 관계, 선후행 관계를 표현하는 데 적합하다. 위상 정렬(Topological Sort)로 실행 순서를 결정할 수 있다. Airflow, Bazel, Gradle, npm, Terraform, Spark가 전부 내부적으로 DAG를 사용한다. "선행 작업이 완료되어야 후속 작업을 시작할 수 있다"는 패턴은 모두 DAG로 모델링된다.
그럼 어떤 순서로 실행해야 하나 - 순서 문제 풀기¶
사이클이 없다는 건 줄 세우기가 가능하다는 뜻이고, 실무가 진짜 원하는 건 그 실행 순서다. DAG에서 "의존성 순서대로 나열하기"가 위상 정렬이다.
위상 정렬 결과: A → B → C → D 또는 A → C → B → D (둘 다 유효)
"A를 먼저 해야 B를 할 수 있다" 류의 순서를 정하는 거다. npm이 패키지를 설치하는 순서, Gradle이 모듈을 빌드하는 순서, Airflow가 Task를 실행하는 순서가 전부 위상 정렬이다.
Kahn's Algorithm - BFS 기반 위상 정렬¶
가장 직관적인 위상 정렬 알고리즘이 Kahn's Algorithm이다. 핵심 아이디어는 "진입 차수(in-degree)가 0인 노드부터 처리"다.
진입 차수란 "이 노드로 들어오는 간선의 개수"다. 진입 차수가 0이라는 건 "선행해야 할 작업이 없다"는 뜻이다.
from collections import deque
def topological_sort(graph):
# 1단계: 진입 차수(in-degree) 계산
in_degree = {node: 0 for node in graph}
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] = in_degree.get(neighbor, 0) + 1
# 2단계: 진입 차수 0인 노드를 모두 큐에 넣는다 (시작 가능한 작업)
queue = deque([n for n in in_degree if in_degree[n] == 0])
result = []
# 3단계: 큐에서 하나씩 꺼내며 처리
while queue:
node = queue.popleft()
result.append(node)
# 이 노드를 완료했으니 후속 노드의 진입 차수를 1 감소
for neighbor in graph.get(node, []):
in_degree[neighbor] -= 1
# 후속 노드도 시작 가능해지면 큐에 추가
if in_degree[neighbor] == 0:
queue.append(neighbor)
# 4단계: 모든 노드를 처리하지 못했다면 사이클이 있다는 뜻
if len(result) != len(in_degree):
raise ValueError("사이클이 존재합니다!")
return result
동작 원리:
- 처음에 "아무도 의존하지 않는 노드"(in-degree 0)를 큐에 넣는다
- 큐에서 노드를 꺼내 결과에 추가하고, 그 노드가 가리키는 후속 노드들의 in-degree를 1씩 감소시킨다
- in-degree가 0이 된 후속 노드를 큐에 추가한다
- 큐가 빌 때까지 반복한다
결과 길이가 전체 노드 수와 다르면, 어딘가에 사이클이 있다는 뜻이다. 사이클 안의 노드는 in-degree가 영원히 0이 되지 않으니까 큐에 들어가지 못한다.
(이걸 역으로 이용해서 사이클 감지에 쓸 수 있다. 위에서 본 DFS 기반 사이클 탐지와 동등한 결과를 낸다.)
Topological Sort (위상 정렬)
DAG에서 간선의 방향을 거스르지 않으면서 모든 노드를 나열하는 알고리즘이다. "선행 조건을 먼저 처리"하는 순서를 결정한다. BFS 기반(Kahn's Algorithm)과 DFS 기반(역순 후위 순회) 두 가지 방법이 있다. 빌드 시스템, 패키지 매니저, 작업 스케줄러에서 핵심적으로 사용된다. 사이클이 있으면 위상 정렬이 불가능하므로, 사이클 탐지 도구로도 쓰인다.
In-degree / Out-degree (진입 차수 / 진출 차수)
방향 그래프에서 한 노드로 들어오는 간선의 수가 in-degree, 나가는 간선의 수가 out-degree다. Kahn's Algorithm의 핵심 개념으로, in-degree가 0이라는 건 "선행 조건이 없는 노드"라는 뜻이다.
정말 그 순서가 나오는지 손으로 따라가보면¶
코드만 보면 미덥지 않으니, 빌드 의존성 예시로 동작을 한 단계씩 따라가보자.
graph LR
UTILS["utils"] --> API["api"]
UTILS --> WORKER["worker"]
API --> INT_TEST["integration-test"]
WORKER --> INT_TEST
INT_TEST --> DEPLOY["deploy"]| 단계 | 큐 상태 | 결과 | in-degree 변화 |
|---|---|---|---|
| 초기 | [utils] | [] | utils=0, api=1, worker=1, integration-test=2, deploy=1 |
| 1 | [api, worker] | [utils] | api=0, worker=0 |
| 2 | [worker, integration-test가 아직 1] | [utils, api] | integration-test=1 |
| 3 | [integration-test] | [utils, api, worker] | integration-test=0 |
| 4 | [deploy] | [utils, api, worker, integration-test] | deploy=0 |
| 5 | [] | [utils, api, worker, integration-test, deploy] | - |
빌드 순서는 utils → api → worker → integration-test → deploy. api와 worker는 의존 관계가 없으니까 병렬 실행도 가능하다. CI 시스템이 이걸 보고 자동으로 병렬화한다.