그래프나 트리를 탐색할 때 우리는 어떤 순서로 노드를 방문해야 할까요? 미로에서 길을 찾을 때 "일단 한 길을 끝까지 가보고, 막히면 돌아와서 다른 길을 시도한다"는 생각을해볼것같아요.
이것이 바로 DFS(깊이 우선 탐색, Depth-First Search)의 핵심 아이디어라고 합니다.
DFS는 그래프 탐색의 가장 기본적인 알고리즘 중 하나로, 백준이나 프로그래머스 같은 코딩 테스트에서 매우 자주 등장합니다. 특히 "경로 찾기", "연결 요소 개수 구하기", "사이클 판별" 같은 문제에서 필수적으로 사용됩니다.
DFS란?
DFS는 한 방향으로 끝까지 탐색한 후, 더 이상 갈 곳이 없으면 되돌아와서 다른 경로를 탐색하는 알고리즘입니다.
기본 원리?
- 시작 노드를 방문하고 방문 표시를 합니다.
- 현재 노드와 인접한 미방문 노드 중 하나를 선택합니다.
- 선택한 노드로 이동하여 1~2를 반복합니다.
- 더 이상 갈 곳이 없으면 이전 노드로 되돌아갑니다(백트래킹).
- 모든 노드를 방문할 때까지 반복합니다.
실생활에 대입해보자.
미로 탐색을 생각해봅시다.
- 출발점에서 시작합니다.
- 갈림길이 나오면 한 방향을 선택합니다.
- 선택한 길을 끝까지 갑니다.
- 막다른 길에 도달하면 가장 최근 갈림길로 돌아옵니다.
- 다른 길을 시도합니다.
이 방식은 우리가 본능적으로 미로를 탐색할 때 사용하는 방법과 매우 유사합니다.
복잡도
시간 복잡도
- V: 정점(Vertex)의 개수
- E: 간선(Edge)의 개수
O(V + E)
모든 정점을 한 번씩 방문하고, 모든 간선을 한 번씩 확인하므로 O(V + E)의 시간 복잡도를 가집니다.
공간 복잡도
- 재귀 구현: O(V) - 재귀 호출 스택
- 스택 구현: O(V) - 명시적 스택 + 방문 배열
DFS 구현 방법
DFS는 크게 두 가지 방법 재귀, 스택으로 구현할 수 있습니다. 말로 설명하는것보다 코드로 바로 작성해보도록 하겠습니다.
1. 재귀를 이용한 구현
def dfs_recursive(graph, node, visited):
"""
재귀를 이용한 DFS
Args:
graph: 인접 리스트로 표현된 그래프
node: 현재 방문 중인 노드
visited: 방문 여부를 저장하는 리스트
"""
# 현재 노드 방문 처리
visited[node] = True
print(node, end=' ')
# 인접한 노드들을 재귀적으로 방문
for neighbor in graph[node]:
if not visited[neighbor]:
dfs_recursive(graph, neighbor, visited)
# 사용 예제
if __name__ == "__main__":
# 그래프를 인접 리스트로 표현
graph = {
1: [2, 3],
2: [1, 4, 5],
3: [1, 6, 7],
4: [2],
5: [2],
6: [3],
7: [3]
}
# 방문 여부를 저장할 딕셔너리 (노드 번호가 1부터 시작)
visited = {i: False for i in range(1, 8)}
print("DFS 탐색 순서:")
dfs_recursive(graph, 1, visited)
실행 결과
DFS 탐색 순서:
1 2 4 5 3 6 7
2. 스택을 이용한 구현
명시적인 스택을 사용하여 재귀 없이 구현할 수 있습니다.
def dfs_stack(graph, start):
"""
스택을 이용한 DFS
Args:
graph: 인접 리스트로 표현된 그래프
start: 시작 노드
"""
visited = {i: False for i in graph.keys()}
stack = [start]
result = []
while stack:
# 스택에서 노드 꺼내기
node = stack.pop()
# 아직 방문하지 않은 노드라면
if not visited[node]:
visited[node] = True
result.append(node)
# 인접 노드를 스택에 추가 (역순으로 추가하여 작은 번호부터 방문)
for neighbor in reversed(graph[node]):
if not visited[neighbor]:
stack.append(neighbor)
return result
# 사용 예제
if __name__ == "__main__":
graph = {
1: [2, 3],
2: [1, 4, 5],
3: [1, 6, 7],
4: [2],
5: [2],
6: [3],
7: [3]
}
result = dfs_stack(graph, 1)
print("DFS 탐색 순서:", ' '.join(map(str, result)))
실행 결과
DFS 탐색 순서: 1 2 4 5 3 6 7
재귀 vs 스택 구현 비교
재귀 구현의 장점
- 코드가 간결하고 이해하기 쉽습니다.
- 백트래킹 로직이 자동으로 처리됩니다.
- 대부분의 코딩 테스트에서 선호됩니다.
재귀 구현의 단점
- 재귀 깊이가 너무 깊으면 스택 오버플로우 발생 가능
- Python의 기본 재귀 한도는 약 1000
스택 구현의 장점
- 재귀 한도 제한이 없습니다.
- 메모리 사용을 더 세밀하게 제어할 수 있습니다.
스택 구현의 단점
- 코드가 재귀보다 복잡합니다.
- 방문 순서가 재귀와 다를 수 있습니다.
DFS 동작 과정 시각화
다음 그래프를 DFS로 탐색하는 과정을 단계별로 살펴봅시다.
그래프 구조:
1
/ \
2 3
/ \ / \
4 5 6 7
def dfs_with_visualization(graph, node, visited, depth=0):
"""
DFS 동작 과정을 시각화하는 함수
"""
# 들여쓰기로 깊이 표현
indent = " " * depth
print(f"{indent}→ 노드 {node} 방문")
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
print(f"{indent} 노드 {node}에서 노드 {neighbor}로 이동")
dfs_with_visualization(graph, neighbor, visited, depth + 1)
print(f"{indent} 노드 {neighbor}에서 노드 {node}로 복귀")
# 사용 예제
if __name__ == "__main__":
graph = {
1: [2, 3],
2: [1, 4, 5],
3: [1, 6, 7],
4: [2],
5: [2],
6: [3],
7: [3]
}
visited = {i: False for i in range(1, 8)}
print("=== DFS 동작 과정 ===")
dfs_with_visualization(graph, 1, visited)
실행 결과
=== DFS 동작 과정 ===
→ 노드 1 방문
노드 1에서 노드 2로 이동
→ 노드 2 방문
노드 2에서 노드 4로 이동
→ 노드 4 방문
노드 4에서 노드 2로 복귀
노드 2에서 노드 5로 이동
→ 노드 5 방문
노드 5에서 노드 2로 복귀
노드 2에서 노드 1로 복귀
노드 1에서 노드 3으로 이동
→ 노드 3 방문
노드 3에서 노드 6으로 이동
→ 노드 6 방문
노드 6에서 노드 3으로 복귀
노드 3에서 노드 7로 이동
→ 노드 7 방문
노드 7에서 노드 3으로 복귀
노드 3에서 노드 1로 복귀
이 출력을 보면 DFS가 어떻게 한 방향으로 끝까지 탐색하고, 되돌아와서 다른 경로를 탐색하는지 명확히 알 수 있습니다.
그래프 표현 방법
DFS를 구현하기 전에 그래프를 어떻게 표현할지 결정해야 합니다.
1. 인접 리스트 (Adjacency List) - 추천
각 노드에 연결된 노드들을 리스트로 저장합니다.
# 딕셔너리를 이용한 인접 리스트
graph_dict = {
1: [2, 3],
2: [1, 4, 5],
3: [1, 6, 7],
4: [2],
5: [2],
6: [3],
7: [3]
}
# 리스트를 이용한 인접 리스트 (노드 번호가 0부터 시작)
graph_list = [
[], # 0번 노드 (사용 안 함)
[2, 3], # 1번 노드
[1, 4, 5], # 2번 노드
[1, 6, 7], # 3번 노드
[2], # 4번 노드
[2], # 5번 노드
[3], # 6번 노드
[3] # 7번 노드
]
장점
- 메모리 효율적 (O(V + E))
- 인접 노드 순회가 빠름
- 희소 그래프(sparse graph)에 적합
단점
- 두 노드의 연결 여부 확인이 느림 (O(V))
2. 인접 행렬 (Adjacency Matrix)
2차원 배열로 노드 간 연결을 표현합니다.
# 7개 노드 (1~7번)
INF = float('inf')
graph_matrix = [
[0, 0, 0, 0, 0, 0, 0, 0], # 0번 (사용 안 함)
[0, 0, 1, 1, 0, 0, 0, 0], # 1번 노드
[0, 1, 0, 0, 1, 1, 0, 0], # 2번 노드
[0, 1, 0, 0, 0, 0, 1, 1], # 3번 노드
[0, 0, 1, 0, 0, 0, 0, 0], # 4번 노드
[0, 0, 1, 0, 0, 0, 0, 0], # 5번 노드
[0, 0, 0, 1, 0, 0, 0, 0], # 6번 노드
[0, 0, 0, 1, 0, 0, 0, 0] # 7번 노드
]
장점
- 두 노드의 연결 여부를 O(1)에 확인 가능
- 가중치 그래프 표현이 직관적
- 밀집 그래프(dense graph)에 적합
단점
- 메모리 낭비 (O(V²))
- 인접 노드를 찾으려면 모든 노드를 확인해야 함
어떤 방법을 선택해야 할까?
대부분의 경우 인접 리스트를 사용하는 것이 좋습니다.
- 코딩 테스트에서는 보통 희소 그래프가 주어집니다.
- 메모리와 시간 효율이 더 좋습니다.
- Python의 딕셔너리나 리스트로 쉽게 구현 가능합니다.
DFS 실전 예제
예제 1: 연결 요소의 개수 구하기
그래프에서 서로 연결되어 있지 않은 부분 그래프의 개수를 구하는 문제입니다.
def count_connected_components(n, edges):
"""
연결 요소의 개수를 구하는 함수
Args:
n: 노드의 개수 (1부터 n까지)
edges: 간선 정보 [(u, v), ...]
Returns:
연결 요소의 개수
"""
# 그래프 생성 (인접 리스트)
graph = {i: [] for i in range(1, n + 1)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = {i: False for i in range(1, n + 1)}
count = 0
def dfs(node):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(neighbor)
# 모든 노드에 대해 DFS 수행
for node in range(1, n + 1):
if not visited[node]:
dfs(node)
count += 1
return count
# 사용 예제
if __name__ == "__main__":
n = 6
edges = [(1, 2), (2, 5), (3, 4)]
result = count_connected_components(n, edges)
print(f"연결 요소의 개수: {result}")
# 그래프 시각화
print("\n그래프 구조:")
print("1 - 2 - 5")
print("3 - 4")
print("6 (독립)")
실행 결과
연결 요소의 개수: 3
그래프 구조:
1 - 2 - 5
3 - 4
6 (독립)
동작 과정
1. 노드 1부터 시작 → DFS로 1-2-5 탐색 → count = 1
2. 노드 3 시작 (미방문) → DFS로 3-4 탐색 → count = 2
3. 노드 6 시작 (미방문) → DFS로 6만 탐색 → count = 3
예제 2: 경로 존재 여부 확인
두 노드 사이에 경로가 존재하는지 확인하는 문제입니다.
def has_path(graph, start, end, visited=None):
"""
두 노드 사이의 경로 존재 여부를 확인
Args:
graph: 인접 리스트
start: 시작 노드
end: 목표 노드
visited: 방문 여부 (재귀용)
Returns:
경로가 존재하면 True, 아니면 False
"""
if visited is None:
visited = set()
# 목표 노드에 도달
if start == end:
return True
# 이미 방문한 노드
if start in visited:
return False
visited.add(start)
# 인접 노드 탐색
for neighbor in graph[start]:
if has_path(graph, neighbor, end, visited):
return True
return False
# 사용 예제
if __name__ == "__main__":
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'E'],
'D': ['B'],
'E': ['C'],
'F': ['G'],
'G': ['F']
}
print(f"A에서 E로 가는 경로: {has_path(graph, 'A', 'E')}") # True
print(f"A에서 F로 가는 경로: {has_path(graph, 'A', 'F')}") # False
print(f"F에서 G로 가는 경로: {has_path(graph, 'F', 'G')}") # True
실행 결과
A에서 E로 가는 경로: True
A에서 F로 가는 경로: False
F에서 G로 가는 경로: True
예제 3: 미로 탐색
2차원 배열로 표현된 미로에서 출발점부터 도착점까지의 경로를 찾는 문제입니다.
def solve_maze(maze, start, end):
"""
미로 탐색 (DFS)
Args:
maze: 2차원 리스트 (0: 길, 1: 벽)
start: 시작 좌표 (row, col)
end: 도착 좌표 (row, col)
Returns:
경로가 존재하면 True, 경로 정보 반환
"""
rows, cols = len(maze), len(maze[0])
visited = [[False] * cols for _ in range(rows)]
path = []
def dfs(row, col):
# 범위 체크
if row < 0 or row >= rows or col < 0 or col >= cols:
return False
# 벽이거나 이미 방문한 경우
if maze[row][col] == 1 or visited[row][col]:
return False
# 현재 위치 방문 처리
visited[row][col] = True
path.append((row, col))
# 도착 지점 도달
if (row, col) == end:
return True
# 상하좌우 탐색
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dr, dc in directions:
if dfs(row + dr, col + dc):
return True
# 백트래킹 (막다른 길)
path.pop()
return False
found = dfs(start[0], start[1])
return found, path if found else []
# 사용 예제
if __name__ == "__main__":
# 0: 길, 1: 벽
maze = [
[0, 0, 0, 1, 0],
[1, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]
]
start = (0, 0)
end = (4, 4)
found, path = solve_maze(maze, start, end)
if found:
print("경로를 찾았습니다!")
print(f"경로: {path}")
print(f"경로 길이: {len(path)}")
# 미로 시각화 (경로 표시)
print("\n미로 (경로는 *로 표시):")
for i in range(len(maze)):
for j in range(len(maze[0])):
if (i, j) in path:
print("* ", end="")
elif maze[i][j] == 1:
print("■ ", end="")
else:
print(". ", end="")
print()
else:
print("경로를 찾을 수 없습니다.")
실행 결과
경로를 찾았습니다!
경로: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)]
경로 길이: 9
미로 (경로는 *로 표시):
* * * ■ .
■ ■ * ■ .
. . * * *
. ■ ■ ■ *
. . . . *
DFS 활용 분야
1. 경로 찾기
- 두 노드 사이의 경로 존재 여부
- 모든 경로 찾기
- 최단 경로 (가중치 없는 그래프에서는 BFS가 더 적합)
2. 사이클 탐지
- 무향 그래프의 사이클
- 유향 그래프의 사이클
- 위상 정렬
def has_cycle(graph, n):
"""
무향 그래프에서 사이클 존재 여부 확인
"""
visited = [False] * (n + 1)
def dfs(node, parent):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
if dfs(neighbor, node):
return True
elif neighbor != parent:
# 부모가 아닌 방문한 노드 → 사이클
return True
return False
for i in range(1, n + 1):
if not visited[i]:
if dfs(i, -1):
return True
return False
3. 위상 정렬
선행 관계가 있는 작업들의 순서를 결정하는 문제입니다.
def topological_sort(graph, n):
"""
위상 정렬 (DFS 기반)
"""
visited = [False] * (n + 1)
stack = []
def dfs(node):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(neighbor)
# 후위 순회: 현재 노드를 스택에 추가
stack.append(node)
for i in range(1, n + 1):
if not visited[i]:
dfs(i)
# 스택을 역순으로 반환
return stack[::-1]
4. 연결 요소
- 연결 요소의 개수
- 각 연결 요소의 크기
- 강한 연결 요소 (Strongly Connected Components)
5. 미로/퍼즐 탐색
DFS의 장단점
장점
- 구현이 간단합니다 (재귀 사용 시)
- 현재 경로의 노드만 기억하므로 메모리 효율적
- 백트래킹과 자연스럽게 결합됨
- 모든 경로를 탐색해야 하는 경우 유용
단점
- 최단 경로를 보장하지 않음
- 재귀 깊이가 깊어지면 스택 오버플로우 위험
- 무한 루프 가능성 (사이클이 있고 방문 체크를 안 하면)
DFS 체크 포인트
1. 방문 체크 누락
DFS에서 가장 흔한 실수는 방문 체크를 빼먹는 것입니다.
# 잘못된 코드 (무한 루프)
def wrong_dfs(graph, node):
print(node)
for neighbor in graph[node]:
wrong_dfs(graph, neighbor) # 방문 체크 없음!
# 올바른 코드
def correct_dfs(graph, node, visited):
if visited[node]:
return
visited[node] = True
print(node)
for neighbor in graph[node]:
if not visited[neighbor]:
correct_dfs(graph, neighbor, visited)
2. 재귀 깊이 제한
Python의 기본 재귀 한도는 약 1000입니다.
import sys
# 재귀 한도 증가 (필요한 경우)
sys.setrecursionlimit(10000)
# 또는 스택을 사용한 반복 구현으로 변경
3. 양방향 간선 처리
무향 그래프에서는 양방향으로 간선을 추가해야 합니다.
# 무향 그래프
edges = [(1, 2), (2, 3), (3, 4)]
graph = {i: [] for i in range(1, 5)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # 양방향!
4. 방문 배열 초기화
여러 번 DFS를 수행할 때는 방문 배열을 초기화해야 합니다.
# 방법 1: 새로운 방문 배열 생성
visited = [False] * n
# 방법 2: 기존 배열 초기화
visited = [False] * n
# DFS 수행...
visited = [False] * n # 재초기화
DFS vs BFS 비교
| 특징 |
DFS |
BFS |
| 탐색 방식 |
깊이 우선 |
너비 우선 |
| 구현 |
재귀 or 스택 |
큐 |
| 메모리 |
O(h) - 높이만큼 |
O(w) - 너비만큼 |
| 최단 경로 |
보장 안 됨 |
보장됨 |
| 적합한 문제 |
경로 존재 여부, 백트래킹 |
최단 거리, 레벨 탐색 |
언제 DFS를 사용해야 할까?
- 모든 경로를 탐색해야 할 때
- 백트래킹이 필요할 때
- 메모리가 제한적일 때
- 경로의 특징을 찾아야 할 때
언제 BFS를 사용해야 할까?
- 최단 경로를 찾아야 할 때
- 레벨별로 탐색해야 할 때
- 가까운 노드부터 확인해야 할 때
마치며
DFS를 처음 배웠을 때는 이름부터 생소하고 단순 "재귀가 어렵다"는 생각이 들었습니다. 하지만 직접 손으로 그래프를 그려보고, 코드를 작성하면서 "한 방향으로 끝까지 가고, 막히면 돌아온다"는 단순한 원리를 이해하게 되었습니다.
특히 미로 탐색 예제를 직접 구현해보면서, 우리가 본능적으로 미로를 탐색하는 방식과 DFS가 얼마나 유사한지 깨달았습니다. 알고리즘은 결국 우리의 직관을 체계화한 것이라는 생각이 들었습니다.
실무에서는 DFS를 직접 구현하기보다는, 그래프 라이브러리나 프레임워크를 사용하는 경우가 많습니다. 하지만 DFS의 원리를 이해하면 복잡한 문제를 분해하고 해결하는 사고방식을 기를 수 있습니다.
코딩 테스트에서는 DFS가 매우 자주 등장합니다. 특히 "연결 요소 개수", "경로 찾기", "사이클 판별" 같은 문제는 DFS의 기본 패턴만 익히면 쉽게 풀 수 있습니다.
다음 포스팅에서는 DFS와 함께 그래프 탐색의 양대 산맥인 BFS(너비 우선 탐색) 에 대해 포스팅하려고합니다. DFS가 "깊이"를 우선한다면, BFS는 "너비"를 우선합니다. 두 알고리즘을 비교하면서 공부하면 더욱 명확하게 이해할 수 있을 것입니다!!
