[알고리즘] DFS(깊이 우선 탐색)

DFS (Depth-First Search) 깊이 우선 탐색

DFS는 그래프 탐색 알고리즘 중 하나로
시작 노드에서 가능한 깊이까지 먼저 탐색한 뒤
더 이상 깊게 갈 곳이 없을 경우 되돌아가며(Backtracking) 탐색을 이어가는 방식입니다.

 

DFS 특징

• 방문 경로를 깊이 우선으로 추적
• 재귀 호출 또는 스택(Stack)을 활용해 구현 가능
• 그래프의 연결 요소 탐색에 유용
• 순환 구조(사이클)나 미로 찾기 문제 등에 자주 사용됨

 

DFS vs BFS

구분	DFS	BFS
자료구조	스택(Stack) or 재귀	큐(Queue)
방문 순서	깊이 우선 → 다음 분기로 이동	너비 우선 → 레벨 순서대로 이동
구현 방식	주로 재귀 또는 수동 스택	큐로 구현
사용 예시	백트래킹, 미로, 트리 탐색 등	최단 거리, 레벨 기반 탐색 등

 

DFS 알고리즘 구현

DFS는 다음과 같은 구조로 동작합니다:

 

1. 시작 노드를 needVisit 스택에 넣음
2. 스택에서 노드를 꺼내고, 아직 방문하지 않았다면 visited 목록에 추가
3. 해당 노드의 인접 노드를 다시 needVisit 스택에 넣음
4. 반복

BFS는 두 개의 큐를 활용하는데 반해
DFS는 스택과 큐를 활용한다는 차이가 있음을 인지해야 함

---

Java 코드

import java.util.*;

public class DFSExample {

    public static List<String> dfs(Map<String, List<String>> graph, String startNode) {
        List<String> visited = new ArrayList<>();
        Stack<String> needVisit = new Stack<>();
        needVisit.push(startNode);

        while (!needVisit.isEmpty()) {
            String node = needVisit.pop();
            if (!visited.contains(node)) {
                visited.add(node);
                List<String> neighbors = graph.getOrDefault(node, new ArrayList<>());
                // 뒤에 있는 노드가 먼저 방문되도록 역순으로 push
                List<String> reversed = new ArrayList<>(neighbors);
                Collections.reverse(reversed);
                for (String neighbor : reversed) {
                    needVisit.push(neighbor);
                }
            }
        }

        return visited;
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("D", "G"));
        graph.put("C", Arrays.asList("E", "F"));
        graph.put("D", Arrays.asList("G"));
        graph.put("E", new ArrayList<>());
        graph.put("F", new ArrayList<>());
        graph.put("G", Arrays.asList("H", "I"));
        graph.put("H", new ArrayList<>());
        graph.put("I", Arrays.asList("J"));
        graph.put("J", new ArrayList<>());

        List<String> result = dfs(graph, "A");
        System.out.println("DFS 탐색 결과: " + result);
    }
}

---

시간 복잡도

DFS의 시간 복잡도는 다음과 같이 계산됩니다:

• 노드 수(V): 각 노드를 한 번씩 방문
• 간선 수(E): 각 간선을 한 번씩 탐색
• 위 코드에서 `while (!needVisit.isEmpty())`은 `V + E` 번 만큼 수행함

따라서 시간 복잡도는 `O(V + E)` 입니다.

 

DFS 요약

항목	설명
구현 방식	재귀 or 스택
탐색 순서	깊이 우선 (Backtracking)
시간 복잡도	`O(V + E)`
용도	사이클 탐지, 경로 탐색, 백트래킹 등