DFS & BFS
DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프의 정점을 빠짐없이 방문하는 가장 기본적인 두 가지 방법입니다.
한눈에 보기
둘 다 그래프 알고리즘으로, 문제를 풀 때 아주 많이 쓰입니다. 경로를 찾는 문제에서는 상황에 맞게 DFS와 BFS 중 하나를 고릅니다.
- 그래프: 점(정점, vertex)과 점을 잇는 선(간선, edge)으로 이루어진 구조입니다. 지하철 노선도를 떠올리면 됩니다. 역이 정점, 역 사이 선로가 간선입니다.
- DFS: 미로에서 한 길을 골라 막다른 곳까지 쭉 들어가 보고, 막히면 되돌아와 다른 길로 가는 방식입니다.
- BFS: 호수에 돌을 던졌을 때 물결이 퍼지듯, 가까운 곳부터 한 겹씩 넓혀 가는 방식입니다.
| 구분 | DFS (깊이 우선) | BFS (너비 우선) |
|---|---|---|
| 방문 순서 | 한 가지(브랜치)를 끝까지 탐색한 뒤 다음 가지로 | 시작점과 가까운(인접한) 정점부터 |
| 구현 도구 | 스택 또는 재귀 함수 | 큐 |
| 잘 맞는 경우 | 모든 경로를 방문해야 할 때 | 간선 수 기준 최단 경로(최소 이동 횟수)를 찾을 때 |
DFS (깊이 우선 탐색)
루트 노드 혹은 임의의 노드에서 출발해, 다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색하는 방법입니다.
스택 또는 재귀 함수로 구현합니다. 방금 들어온 길을 거꾸로 되돌아 나와야 하므로 "마지막에 넣은 것을 먼저 꺼내는" 스택이 딱 맞습니다. 재귀 함수도 내부적으로 호출 스택을 쓰므로 같은 원리입니다.
- 모든 경로를 방문해야 할 경우에 적합합니다.
동작 과정
- 시작 정점을 방문 표시합니다.
- 방문하지 않은 이웃 중 하나(보통 번호가 작은 것)로 들어갑니다.
- 들어간 정점에서 다시 1~2를 반복합니다.
- 더 갈 이웃이 없으면 직전 정점으로 되돌아가서 남은 이웃을 봅니다.
- 모든 정점에서 더 갈 곳이 없으면 끝납니다.
예시 그래프: 정점 4개, 간선 1-2, 1-3, 1-4, 2-4, 3-4, 시작 정점 1
| 단계 | 현재 정점 | 지나온 경로 | 설명 |
|---|---|---|---|
| 1 | 1 | 1 | 1 방문. 이웃 2, 3, 4 중 가장 작은 2로 |
| 2 | 2 | 1 → 2 | 2 방문. 이웃 1은 방문함, 4로 |
| 3 | 4 | 1 → 2 → 4 | 4 방문. 이웃 1, 2는 방문함, 3으로 |
| 4 | 3 | 1 → 2 → 4 → 3 | 3 방문. 이웃 1, 4 모두 방문함 |
| 5 | - | 되돌아감 | 3 → 4 → 2 → 1로 되돌아가도 남은 이웃 없음, 종료 |
방문 순서: 1 → 2 → 4 → 3
그림으로 보기
그림 출처: Wikimedia Commons
Python 코드 (재귀)
원문 C 코드처럼 인접 행렬(graph[a][b] == 1이면 a와 b가 연결됨)을 쓰고, 번호가 작은 이웃부터 방문합니다.
def dfs(graph, v, visited, order):
"""재귀로 구현한 DFS. graph는 인접 행렬, 정점 번호는 1부터"""
visited[v] = True # 1. 현재 정점 방문 표시
order.append(v)
for nxt in range(1, len(graph)): # 2. 번호가 작은 이웃부터 확인
if graph[v][nxt] == 1 and not visited[nxt]:
dfs(graph, nxt, visited, order) # 3. 그 이웃 쪽 가지를 끝까지 탐색
def build(n, edges):
"""간선 목록으로 무방향 인접 행렬 만들기"""
graph = [[0] * (n + 1) for _ in range(n + 1)]
for a, b in edges:
graph[a][b] = graph[b][a] = 1
return graph
n = 4
graph = build(n, [(1, 2), (1, 3), (1, 4), (2, 4), (3, 4)])
order = []
dfs(graph, 1, [False] * (n + 1), order)
print(*order) # 출력: 1 2 4 3- 들어오자마자 방문 표시를 해야 같은 정점을 두 번 방문하지 않습니다.
- 1번부터 차례로 보므로 이웃이 여러 개면 번호가 작은 쪽이 먼저입니다.
- 방문하지 않은 이웃을 찾으면 곧바로 그쪽으로 깊이 들어갑니다. 그 호출이 끝나야(막다른 곳까지 갔다 와야) 다음 이웃을 봅니다.
Python은 기본 재귀 깊이 제한이 약 1000입니다. 정점이 많으면 sys.setrecursionlimit(10000)처럼 늘리거나, 아래 스택 버전을 씁니다.
Python 코드 (스택)
def dfs_stack(graph, start):
"""스택으로 구현한 DFS. 재귀 버전과 같은 순서로 방문"""
n = len(graph) - 1
visited = [False] * (n + 1)
order = []
stack = [start] # 1. 시작 정점을 스택에 넣기
while stack:
v = stack.pop() # 2. 가장 최근에 넣은 정점 꺼내기
if visited[v]:
continue
visited[v] = True
order.append(v)
for nxt in range(n, 0, -1): # 3. 큰 번호부터 넣어야 작은 번호가 먼저 나옴
if graph[v][nxt] == 1 and not visited[nxt]:
stack.append(nxt)
return order
print(*dfs_stack(graph, 1)) # 출력: 1 2 4 3- 스택은 "나중에 넣은 것을 먼저 꺼내는" 통입니다. Python에서는 리스트의
append/pop으로 충분합니다. - 꺼낸 정점이 이미 방문한 것이면 건너뛰고, 아니면 방문 표시합니다. 같은 정점이 스택에 여러 번 들어갈 수 있어서 꺼낼 때 확인합니다.
- 스택은 거꾸로 나오므로, 작은 번호를 먼저 방문하려면 큰 번호부터 넣습니다.
BFS (너비 우선 탐색)
루트 노드 또는 임의의 노드에서 출발해, 인접한 노드부터 먼저 탐색하는 방법입니다.
큐로 구현합니다. 해당 노드의 주변부터 탐색해야 하므로, "먼저 넣은 것을 먼저 꺼내는" 큐가 맞습니다. 은행 번호표처럼 먼저 온 순서대로 처리됩니다.
- 최소 비용이 우선일 때, 즉 모든 곳을 다 탐색하는 것보다 가장 적은 이동 횟수로 도착하는 길을 찾을 때 적합합니다. BFS는 처음 도달한 순간이 곧 최단 거리(간선 수 기준)입니다. 간선마다 비용이 다르면 BFS가 아니라 다익스트라를 씁니다.
동작 과정
- 시작 정점을 방문 표시하고 큐에 넣습니다.
- 큐 맨 앞의 정점을 꺼냅니다.
- 그 정점의 이웃 중 방문하지 않은 것을 모두 방문 표시하고 큐 뒤에 넣습니다.
- 큐가 빌 때까지 2~3을 반복합니다.
같은 예시 그래프, 시작 정점 1
| 단계 | 꺼낸 정점 | 새로 넣은 정점 | 큐 상태 | 방문 순서 |
|---|---|---|---|---|
| 시작 | - | 1 | [1] | 1 |
| 1 | 1 | 2, 3, 4 | [2, 3, 4] | 1, 2, 3, 4 |
| 2 | 2 | 없음 (1, 4 방문함) | [3, 4] | 1, 2, 3, 4 |
| 3 | 3 | 없음 | [4] | 1, 2, 3, 4 |
| 4 | 4 | 없음 | [] | 1, 2, 3, 4 |
방문 순서: 1 → 2 → 3 → 4 (시작점에서 거리 1인 2, 3, 4가 한꺼번에 먼저 방문됨)
그림으로 보기
그림 출처: Wikimedia Commons
Python 코드
from collections import deque
def bfs(graph, start):
"""큐로 구현한 BFS. graph는 인접 행렬, 정점 번호는 1부터"""
n = len(graph) - 1
visited = [False] * (n + 1)
order = [start]
queue = deque([start]) # 1. 시작 정점을 큐에 넣고 방문 표시
visited[start] = True
while queue:
v = queue.popleft() # 2. 먼저 들어온 정점부터 꺼내기
for nxt in range(1, n + 1):
if graph[v][nxt] == 1 and not visited[nxt]:
visited[nxt] = True # 3. 큐에 넣는 순간 방문 표시
order.append(nxt)
queue.append(nxt)
return order
print(*bfs(graph, 1)) # 출력: 1 2 3 4deque는 앞뒤에서 넣고 빼기가 빠른 Python 표준 큐입니다. 리스트의pop(0)은 매번 나머지를 한 칸씩 당기느라 느립니다(O(n)).popleft()로 가장 먼저 들어온 정점을 꺼내므로 가까운 정점부터 처리됩니다.- 꺼낼 때가 아니라 넣을 때 방문 표시를 해야, 같은 정점이 큐에 여러 번 들어가지 않습니다.
DFS와 BFS 한눈에 비교
| 구분 | DFS (Depth-First Search) | BFS (Breadth-First Search) |
|---|---|---|
| 이름 | 깊이 우선 탐색 | 너비 우선 탐색 |
| 방식 | 한 방향으로 끝까지 내려가 탐색 | 가까운 노드부터 층별로 탐색 |
| 자료구조 | 스택 (LIFO / 후입선출) | 큐 (FIFO / 선입선출) |
예시 1 (A의 자식 B, C / B의 자식 D)
- DFS:
A → B → D → C(D까지 내려갔다가 B, A로 되돌아온 뒤 C) - BFS:
A → B → C → D
예시 2 (A의 자식 B, C / B의 자식 D, E / C의 자식 F, G)
- DFS:
A → B → D → E → C → F → G - BFS:
A → B → C → D → E → F → G
큐 (BFS): 먼저 들어간 것이 먼저 나옵니다. 예) A → B → C 순서로 넣으면 꺼낼 때도 A → B → C.
데이터 들어감 →
[ C | B | A ]→ 데이터 나감 (오른쪽 A가 맨 앞)
스택 (DFS): 가장 최근에 들어온 것이 맨 위에 있고, 가장 먼저 들어온 것이 맨 아래에 있습니다.
| 스택 상태 (맨 위 → 아래) | 꺼내는 것 |
|---|---|
[B, C] | B 꺼냄 (B의 자식 D를 넣음) |
[D, C] | D 꺼냄 |
[C] | C 꺼냄 |
방문 순서:
A → B → D → C
직접 손으로 정리한 노트: 큐(BFS)와 스택(DFS)
시간복잡도와 공간복잡도
V는 정점(vertex) 수, E는 간선(edge) 수입니다. DFS와 BFS 모두 같습니다.
| 그래프 표현 | 시간복잡도 | 이유 |
|---|---|---|
| 인접 행렬 | O(V²) | 정점마다 모든 정점(V개)과의 연결 여부를 확인 |
| 인접 리스트 | O(V + E) | 정점마다 실제 연결된 이웃만 확인, 간선은 합쳐서 한두 번씩만 봄 |
- 공간복잡도: 방문 표시와 스택/큐에 O(V). 그래프 저장은 인접 행렬 O(V²), 인접 리스트 O(V + E).
- 간선이 적은 그래프라면 인접 리스트가 훨씬 빠르고 메모리도 적게 씁니다. 복잡도 표기는 시간 복잡도 글을 참고하세요.
연습문제
[BOJ] DFS와 BFS: 그래프와 시작 정점이 주어지면 DFS, BFS 방문 순서를 출력하는 문제입니다. 방문할 수 있는 정점이 여러 개면 번호가 작은 것부터 방문합니다. 위 코드가 바로 이 규칙대로 동작합니다.
예) 정점 5개, 시작 정점 3, 간선 5-4, 4-3, 5-2, 1-2, 3-4, 3-1 → DFS 3 1 2 5 4, BFS 3 1 4 2 5
Mini Git에서 써 보기
커밋 그래프를 탐색하는 두 가지 방법, 최단 경로를 찾는 BFS와 조상을 모으는 DFS를 다룹니다.
BFS(너비 우선 탐색) - 최단 경로 찾기
PATH <c1> <c2>: 두 커밋 사이의 가장 짧은 연결(간선 수 최소)을 찾습니다. 단, 커밋-부모 연결을 무방향(양방향으로 오갈 수 있는) 간선으로 봅니다.
BFS = 시작점에서 출발해서 가까운 이웃부터 차례차례 넓혀가며 탐색. 성질: BFS는 처음 도달했을 때가 곧 최단 거리입니다.
필요한 도구:
- 큐(queue): 다음에 방문할 곳 목록. 먼저 넣은 것부터 꺼냄 (
collections금지지만 list의append/pop(0)또는 인덱스 포인터로 구현 가능) - visited 집합: 이미 방문한 커밋 재방문 방지 (사이클 대비)
경로 복원: 큐에 넣을 때 "어디서 왔는지(came_from)"를 기록해두면, 도착점에서 시작점까지 거꾸로 따라가며 경로를 만들 수 있습니다.
동률 처리(요구사항): 최단 경로가 여러 개면 hash1->hash2->... 문자열 기준 사전순 최소 선택. 구현 팁: 이웃을 방문 예약할 때 해시 문자열 순으로 정렬하거나, 같은 거리의 후보들 중 사전순으로 앞선 것을 우선 선택하도록 처리.
DFS/집합 추적 - 조상 찾기
ANCESTORS <hash>: 특정 커밋에서 도달 가능한 모든 부모 쪽 커밋을 전부 출력.
방법: hash에서 출발해 parents를 따라 쭉쭉 방문하면서, 방문한 적 없는 커밋마다 결과에 추가.
def find_ancestors(start):
"""시작 커밋의 모든 조상을 모으는 함수 (BFS/DFS 아무거나)"""
result = []
visited = set()
stack = [start] # DFS는 줄 대신 스택(또는 재귀)
while stack:
cur = stack.pop()
for p in cur.parents:
if p.hash not in visited:
visited.add(p.hash)
result.append(p)
stack.append(p) # 부모의 부모도 계속 탐색
return result핵심은 visited로 중복 방문 막기. 브랜치가 합쳐진 그래프에서는 같은 조상에 여러 경로로 도달하기 때문입니다.
정리
| 개념 | 비전공자 버전 요약 |
|---|---|
| DFS | 한 길을 막다른 곳까지 쭉 가 보고, 막히면 되돌아와 다른 길로 |
| BFS | 가까운 곳부터 넓혀가며 찾는 최단 경로 탐색 |
| 스택 / 큐 | 스택은 나중에 넣은 것 먼저, 큐는 먼저 넣은 것 먼저 꺼냄 |
| visited | 이미 간 곳에 표시해 두어 두 번 가지 않기 |
| 조상 탐색 | 부모 줄기를 끝까지 따라가 전부 모으기 |
출처: Codyssey-B1/B5-2 (학습 노트 포함)