DFS란?
DFS(깊이 우선 탐색, Depth First Search)는 어떤 문제를 해결하기 위해 깊이 있는 곳까지 먼저 탐색하는 방법입니다.
예를 들어, 미로에서 출구를 찾을 때 한 길을 끝까지 가보고, 막히면 다시 돌아와서 다른 길을 찾는 방식과 같습니다. 즉, 갈 수 있을 때까지 계속 가다가 더 이상 갈 곳이 없으면 뒤로 돌아오는 방식입니다.
DFS는 재귀(함수를 자기 자신을 부르는 방식) 또는 스택(뒤에서 추가하고 꺼내는 자료구조)을 사용하여 구현할 수 있습니다.
DFS의 특징
-
하나의 경로를 끝까지 탐색: 갈 수 있는 길이 있으면 끝까지 간 후에 돌아옵니다.
-
스택을 활용: 재귀 방식(함수 호출) 또는 직접 스택을 만들어서 구현할 수 있습니다.
-
백트래킹(되돌아가기): 더 이상 진행할 수 없는 경우 이전 단계로 돌아가 다른 길을 찾습니다.
-
그래프 탐색 가능: 트리뿐만 아니라 복잡한 네트워크에서도 사용할 수 있습니다.
DFS의 동작 원리
-
탐색을 시작할 노드를 선택합니다. (예: A 노드에서 시작)
-
해당 노드를 방문하고, 방문했다고 표시합니다.
-
인접한 노드 중 방문하지 않은 노드를 찾아 재귀적으로 탐색합니다.
-
더 이상 방문할 노드가 없으면, 이전 노드로 되돌아갑니다.
-
모든 노드를 탐색할 때까지 위 과정을 반복합니다.
💡 쉽게 생각하면
-
길이 있으면 계속 갑니다.
-
막히면 돌아옵니다.
-
다른 길이 있으면 또 가봅니다.
-
모든 길을 다 가봤다면 탐색이 끝납니다.
DFS 구현 방법 (예제 코드 포함)
재귀(Recursive) 방식 (간단한 구현)
# 그래프를 리스트(딕셔너리)로 표현
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'E': ['B'],
'F': ['C'],
'G': ['C']
}
visited = set() # 방문한 노드 저장
def dfs_recursive(node):
if node not in visited:
print(node, end=' ') # 방문한 노드 출력
visited.add(node) # 방문 표시
for neighbor in graph[node]: # 연결된 노드 탐색
dfs_recursive(neighbor)
dfs_recursive('A') # A에서 시작스택(Stack)을 이용한 반복(Iterative) 방식
# DFS 반복문 구현
def dfs_iterative(start):
stack = [start] # 탐색할 노드를 저장할 스택
visited = set() # 방문한 노드를 저장할 집합
while stack:
node = stack.pop() # 스택에서 노드 꺼내기
if node not in visited:
print(node, end=' ') # 방문한 노드 출력
visited.add(node) # 방문 표시
stack.extend(reversed(graph[node])) # 방문할 노드 추가
dfs_iterative('A') # A에서 시작DFS의 시간 복잡도
DFS의 시간 복잡도는 O(V + E)입니다.
-
V: 노드(Vertex, 즉 점)의 개수
-
E: 간선(Edge, 즉 선)의 개수
노드와 연결된 선을 한 번씩 방문하기 때문에 V(점) + E(선) 만큼의 시간이 걸립니다.
DFS의 활용 사례
DFS는 여러 가지 문제를 해결하는 데 사용할 수 있습니다.
✅ 미로 탐색: 출구까지의 경로 찾기
✅ 그래프 연결 요소 찾기: 연결된 그룹 찾기
✅ 위상 정렬: 방향 그래프에서의 순서 정하기
✅ 퍼즐 해결: N-Queen 문제, 미로 문제 등
💡 쉽게 말하면: DFS는 길을 찾는 문제나 순서를 정하는 문제에서 유용합니다!
BFS와 DFS 비교
DFS와 비슷한 개념으로 BFS(너비 우선 탐색)가 있습니다.
| 특징 | DFS (깊이 우선 탐색) | BFS (너비 우선 탐색) |
|---|---|---|
| 탐색 방식 | 한 길을 끝까지 탐색 후 돌아감 | 가까운 곳부터 탐색 |
| 자료구조 | 스택 (재귀 또는 직접 구현) | 큐 (Queue) 사용 |
| 최단 경로 보장 | ❌ (돌아가는 경우가 많음) | ✅ (최단 거리 보장) |
| 사용 예시 | 미로 찾기, 퍼즐 해결 | 최단 거리 찾기 |
DFS는 길이 있는 한 깊숙이 탐색하므로 최단 경로를 보장하지 않지만, 퍼즐 해결 같은 문제에서 유용합니다.
결론
DFS는 그래프 탐색을 위한 강력한 알고리즘으로, 깊이 우선으로 탐색하는 방식이 특정 문제 해결에 유용합니다. 재귀와 스택을 활용하여 쉽게 구현할 수 있으며, 다양한 실전 문제에 응용할 수 있습니다.
📌 DFS 핵심 요약
-
길이 있으면 계속 가고, 없으면 되돌아감
-
스택(또는 재귀 함수)을 사용해 구현 가능
-
미로 찾기, 퍼즐 해결 등에서 많이 사용됨
-
최단 경로를 보장하지 않지만, 모든 경로를 찾을 수 있음
BFS와 함께 비교하여 어떤 알고리즘을 사용할지 적절히 선택하는 것이 중요합니다!