-
DFS(Depth-First Search, 깊이 우선 탐색)카테고리 없음 2025. 2. 17. 23:06
DFS는 트리(Tree) 또는 **그래프(Graph)**에서 **깊이(depth)**를 우선으로 탐색하는 알고리즘입니다.
- 최대한 깊이로 내려갔다가 더 이상 탐색할 곳이 없으면 **되돌아오는 방식(백트래킹)**을 사용합니다.
- 스택(Stack) 자료구조(재귀 호출 시 콜 스택(Call Stack) 활용)를 기반으로 동작합니다.
🧠 1️⃣ DFS의 핵심 개념
- 시작 노드에서 최대한 깊이로 내려간다.
- 더 이상 방문할 노드가 없으면 이전 노드로 되돌아감(백트래킹).
- 모든 노드를 방문할 때까지 이 과정을 반복한다.
- 재귀(Recursion) 또는 스택(Stack) 기반
- **트리(Tree)**나 그래프(Graph) 탐색 시 사용
- 순환 탐지(Cycle Detection), 경로 탐색(Path Finding) 등 다양한 응용
🧩 2️⃣ DFS의 자료구조
DFS는 다음과 같은 자료구조를 활용합니다:
자료구조 설명 Stack DFS의 핵심. 재귀 호출 시 콜 스택(Call Stack) 활용 Array **방문 여부(visited 배열)**를 관리하기 위해 사용 Graph 인접 리스트(Adjacency List) 또는 인접 행렬(Adjacency Matrix) 🔍 그래프 표현 방식:
- 인접 리스트(Adjacency List) – 연결된 노드만 저장 → 공간 효율적
- 인접 행렬(Adjacency Matrix) – 2차원 배열로 저장 → 접근 속도 빠름
🔢 3️⃣ DFS 알고리즘 동작 원리
다음 그래프 예제를 기준으로 DFS를 살펴보겠습니다:
🎯 그래프 구조
1
/ \
2 3
/ \ \
4 5 6🛠️ 인접 리스트 표현
1: [2, 3]
2: [4, 5]
3: [6]
4: []
5: []
6: []🚦 DFS 탐색 순서(시작: 1)
1 → 2 → 4 → 5 → 3 → 6
🖥️ 4️⃣ DFS 코드 구현 (Java)
✅ 1. 재귀(Recursive) DFS
import java.util.*;
public class DFSRecursive {
static boolean[] visited;
static List<Integer>[] graph;
public static void main(String[] args) {
// 그래프 초기화
graph = new ArrayList[7]; // 노드: 1~6
for (int i = 1; i <= 6; i++) {
graph[i] = new ArrayList<>();
}
// 그래프 연결
graph[1].add(2); graph[1].add(3);
graph[2].add(4); graph[2].add(5);
graph[3].add(6);
visited = new boolean[7];
// DFS 실행
System.out.print("DFS (재귀): ");
dfs(1);
}
static void dfs(int node) {
visited[node] = true;
System.out.print("node + " ");
for (int next : graph[node]) {
if (!visited[next]) {
dfs(next); // 재귀 호출
}
}
}
}- DFS는 Stack 기반의 깊이 우선 탐색 알고리즘
- Stack 메모리에서 재귀 호출을 통해 DFS 수행
- Spring Framework는 Bean 생성 시 DFS 기반 Component Scan을 사용
- 시간 복잡도: O(V + E), 공간 복잡도: O(V)
- V = Vertices(정점) → 노드 수
- E = Edges(간선) → 연결된 선의 수
DFS는 모든 정점을 한 번씩 방문하고,
각 정점에서 연결된 모든 간선을 확인하기 때문이야.
따라서:
- **노드(V)**를 1번씩 방문 → O(V)
- **각 노드의 간선(E)**을 모두 탐색 → O(E)
O(V + E)