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. 시작 노드를 스택에 push
2. 스택에서 노드를 pop
3. pop된 노드가 방문되지 않았다면 방문 표시하고, 인접 노드를 역순으로 스택에 push
4. 스택이 빌 때까지 반복

 

 

 

 

5)  예시를 통한 동작원리 설명

 

 

STEP 0: Stack = []

시작 노드 A가 pop됨 → 방문

A의 자식들 B, C를 역순으로 push → Stack = [C, B]

 

 

 

STEP 1: Stack = ['C']

B가 pop됨 → 방문

B의 자식 D, E를 역순으로 push → Stack = [C, E, D]

 

 

STEP  Step 2: Stack = ['C', 'E']

D가 pop됨 → 방문 (자식 없음)

Stack = [C, E]

 

 

STEP 3: Stack = ['C']

E가 pop됨 → 방문 (자식 없음)

Stack = [C]

 

 

STEP 4: Stack = []

C가 pop됨 → 방문

C의 자식 F, G를 역순으로 push → Stack = [G, F]

 

 

STEP 5: Stack = ['G']

F가 pop됨 → 방문 (자식 없음)

Stack = [G]

 

 

STEP 6: Stack = []

G가 pop됨 → 방문 (자식 없음)

Stack이 비어 있고, 탐색 종료

 

 

6)  Java로 구현한 DFS 예제 코드

import java.util.*;

public class StackBasedDFS {

    // 인접 리스트 기반 그래프
    private Map<String, List<String>> graph = new HashMap<>();

    // 간선 추가 함수
    public void addEdge(String from, String to) {
        graph.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
    }

    // 스택 기반 DFS 함수
    public void dfs(String start) {
        Set<String> visited = new HashSet<>();
        Stack<String> stack = new Stack<>();

        stack.push(start);

        while (!stack.isEmpty()) {
            String current = stack.pop();

            if (!visited.contains(current)) {
                visited.add(current);
                System.out.println("Visited: " + current);

                // 인접 노드를 역순으로 스택에 push하여 왼쪽 자식부터 탐색
                List<String> neighbors = graph.getOrDefault(current, new ArrayList<>());
                Collections.reverse(neighbors);
                for (String neighbor : neighbors) {
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        StackBasedDFS dfs = new StackBasedDFS();

        // 그래프 구성: A → B,C / B → D,E / C → F,G
        dfs.addEdge("A", "B");
        dfs.addEdge("A", "C");
        dfs.addEdge("B", "D");
        dfs.addEdge("B", "E");
        dfs.addEdge("C", "F");
        dfs.addEdge("C", "G");

        System.out.println("DFS using Stack:");
        dfs.dfs("A");
    }
}

 

DFS using Stack:
Visited: A
Visited: B
Visited: D
Visited: E
Visited: C
Visited: F
Visited: G