시작 노드에서 가능한 깊이까지 탐색한 뒤, 더 이상 갈 곳이 없으면 되돌아(backtrack) 하여 다음 경로를 탐색하는 방식입니다.
한 방향으로 계속 깊게 파고들며, 재귀 또는 스택(Stack)으로 구현 가능하고, 경로 탐색, 조합 탐색, 미로 문제, 백트래킹 등에 유리합니다.
2) DFS 시간복잡도와 공간복잡도
시간복잡도 : O(V + E) V = 정점(노드)의 개수 E = 간선의 개수
공간복잡도 :O(V) 또는 O(h) V = 정점(노드)의 개수 h = 그래프의 최대 깊이
3) DFS 활용분야
활용 분야
설명
경로 찾기
특정 노드까지의 경로 유무, 경로 목록 찾기
미로 탐색
출구가 있는지 확인하거나 모든 경로 탐색
백트래킹 문제
N-Queen, 순열/조합, 스도쿠 해결 등
트리 탐색
전위/중위/후위 순회 구현
사이클 탐지
그래프 내 순환 여부 확인
위상 정렬
DFS 기반 구현 가능 (방문 완료 시점 기록)
연결 요소 탐색
연결된 노드 그룹 찾기 (Connected Components)
4) DFS 동작원리
/ 재귀 방식 /
1. 현재 노드를 방문 표시 2. 인접 노드를 하나씩 확인 3. 방문하지 않은 노드가 있으면 재귀적으로 계속 깊이 탐색 4. 더 이상 갈 곳이 없으면 한 단계 위로 되돌아감
5) 예시를 통한 동작원리 설명
STEP 0: Call Stack = ['A']
시작 노드 A가 호출됨
아직 아무 자식도 탐색하지 않은 상태
다음에 B → C 순서로 탐색 예정 (A의 자식 순서)
STEP 1: Call Stack = ['A', 'B']
A에서 B로 이동
B는 A의 첫 번째 자식 → DFS는 "깊이 우선"이므로 바로 이동
B의 자식 D → E 중에서 D로 먼저 가게 됨
STEP Step 2: Call Stack = ['A', 'B', 'D']
B에서 D로 이동
현재 가장 깊은 곳까지 내려온 상태
D는 자식이 없기 때문에 이후 스택이 빠지기 시작함 (백트래킹)
STEP 3: Call Stack = ['A', 'B', 'E']
D 호출이 끝나고, 다시 B로 백트래킹
이제 B의 두 번째 자식 E 호출
E도 자식 없음 → 곧 B 함수도 종료되고 다시 A로 돌아감
STEP 4: Call Stack = ['A', 'C']
B까지 모두 종료 → A로 백트래킹 후
A의 두 번째 자식 C 호출
이제 C의 자식들로 깊게 내려갈 차례
STEP 5: Call Stack = ['A', 'C', 'F']
C에서 F 호출 (첫 번째 자식)
자식 없음 → 곧 G로 넘어감
STEP 6: Call Stack = ['A', 'C', 'G']
F 호출 종료 → C로 백트래킹 → G 호출
G도 자식 없음 → 전체 DFS 종료
6) Java로 구현한 DFS 예제 코드
import java.util.*;
public class RecursiveDFS {
// 인접 리스트로 그래프 표현
private Map<String, List<String>> graph = new HashMap<>();
// 간선 추가 함수
public void addEdge(String node, String neighbor) {
graph.computeIfAbsent(node, k -> new ArrayList<>()).add(neighbor);
}
// DFS 재귀 함수
public void dfs(String node, Set<String> visited) {
visited.add(node);
System.out.println("Visiting: " + node);
for (String neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
dfs(neighbor, visited);
}
}
}
public static void main(String[] args) {
RecursiveDFS dfs = new RecursiveDFS();
// 그래프 구성
dfs.addEdge("A", "B");
dfs.addEdge("A", "C");
dfs.addEdge("B", "D");
dfs.addEdge("B", "E");
dfs.addEdge("C", "F");
dfs.addEdge("C", "G");
// 방문 집합 생성 및 DFS 실행
Set<String> visited = new HashSet<>();
System.out.println("DFS traversal:");
dfs.dfs("A", visited);
}
}
// 출력결과 //
DFS traversal:
Visiting: A
Visiting: B
Visiting: D
Visiting: E
Visiting: C
Visiting: F
Visiting: G
