DFS 알고리즘(Depth-First Search)

개요

DFS(Depth-First Search)는 트리(Tree)나 그래프(Graph) 구조에서 한 방향으로 깊이 탐색을 진행한 뒤, 더 이상 갈 수 없을 때 되돌아오는(Backtracking) 방식의 탐색 알고리즘이다. 재귀 또는 스택 기반으로 구현되며, 경로 탐색, 조합 생성, 백트래킹, 연결 요소 탐색 등에 널리 사용된다. 본 글에서는 DFS의 개념, 구현 방식, 시간 복잡도, BFS와의 차이, 실전 활용 사례 등을 다룬다.

---

1. 개념 및 정의

DFS는 시작 노드에서 한 방향으로 가능한 깊이까지 탐색하고, 막히면 이전 지점으로 되돌아가 다시 탐색을 이어가는 방식의 탐색 알고리즘이다. 트리 순회(preorder, postorder)나 그래프의 미방문 노드 전체 탐색 등에 사용된다.

---

2. DFS 탐색 방식

단계	설명
1단계	시작 노드를 방문하고 스택에 삽입 (또는 재귀 호출)
2단계	현재 노드에서 방문하지 않은 인접 노드로 이동
3단계	더 이상 방문할 노드가 없으면 스택에서 pop 또는 재귀 복귀
4단계	모든 노드가 방문될 때까지 반복

깊이 우선으로 탐색이 진행되므로 특정 경로의 끝까지 도달하는 데 유리하다.

---

3. DFS 구현 (Python 예시)

# 인접 리스트 기반 DFS 구현

def dfs(graph, node, visited):
    visited.add(node)
    print(node, end=' ')

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 사용 예시
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
visited = set()
dfs(graph, 'A', visited)

DFS는 재귀 호출 또는 명시적인 스택으로 구현할 수 있다.

---

4. 시간 및 공간 복잡도

항목	복잡도
시간 복잡도	O(V + E) (V: 정점 수, E: 간선 수)
공간 복잡도	O(V) (재귀 깊이 또는 스택 공간)

그래프 전체를 한 번씩 방문하므로 효율적인 구조를 갖는다.

---

5. DFS vs BFS 비교

항목	DFS	BFS
탐색 순서	깊이 우선	너비 우선
자료구조	스택 (또는 재귀)	큐
최단 경로 보장	X	O (무가중치 그래프)
메모리 사용	상대적으로 적음	상대적으로 많음
활용 예	백트래킹, 조합, 경로 탐색	최단 거리, 레벨 탐색

문제 성격에 따라 DFS와 BFS 중 적절한 알고리즘을 선택해야 한다.

---

6. 주요 활용 사례

분야	DFS 활용 예시
백트래킹	N-Queen, 퍼즐, 조합 생성
그래프 연결 요소	네트워크 연결 여부 탐색
경로 찾기	특정 경로 존재 여부 확인
트리 순회	전위/후위 순회 구현
인공지능	상태공간 탐색, 의사결정 트리 분석

DFS는 조합과 경로 기반 문제에서 가장 자주 활용되는 알고리즘이다.

---

7. 결론

DFS는 깊이 중심 탐색을 통해 구조화된 자료에서 경로, 조합, 순회 등의 문제를 해결하는 데 매우 효과적인 알고리즘이다. 재귀적 구조와 스택 기반 접근을 통해 직관적이며, 백트래킹과 연결 요소 탐색 등 실전 알고리즘 문제에서 핵심 기법으로 자리 잡고 있다. BFS와 함께 탐색 알고리즘의 기본이자 실전 문제 해결의 출발점이다.