DFS 깊이 우선 탐색 (재귀방식)

DFS

 

 

1)  DFS란?

시작 노드에서 가능한 깊이까지 탐색한 뒤, 더 이상 갈 곳이 없으면 되돌아(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