깊이 우선 탐색(DFS)

1. 깊이 우선 탐색(DFS)이란?

- DFS(Depth-First-Search)는 깊이 우선 탐색 알고리즘으로 그래프나 트리 구조에서 한 경로를 가능한 한 깊게 탐색한 후 더 이상 진행할 수  없으면 이전 단계로 되돌아가 다른 경로를 탐색하는 방식이다.

- 시작 노드에서부터 한 방향으로 깊게 탐색하여 방문한 노드의 자식들 중 아직 방문하지 않은 노드를 우선적으로 탐색한다.

- 주로 재귀나 스택을 활용하여 구현한다.

- O(V+E)의 시간복잡도를 가지며 여기서 V는 정점의 수, E는 간선의 수이다.

1-1. 활용 분야

• 경로 탐색: 그래프에서 특정 노드에 도달하는 경로를 찾거나 모든 경로를 탐색할 때
• 연결 요소 찾기: 그래프의 모든 정점을 방문하여 연결된 구성 요소를 찾을 때
• 백트래킹: 퍼즐, 조합 문제 등에서 모든 가능한 경우를 탐색할 때
• 트리 순회: 전위, 중위, 후위 순회 방식으로 트리구조를 탐색할 때

 

2. DFS 알고리즘 구현

2-1. 재귀 방식 DFS

public class DFSRecursive {
    // 그래프를 인접 리스트로 표현 (정점 번호: 0부터 시작)
    private Map<Integer, List<Integer>> graph;

    public DFSRecursive() {
        graph = new HashMap<>();
    }

    // 그래프에 간선 추가 (무방향 그래프)
    public void addEdge(int src, int dest) {
        graph.computeIfAbsent(src, x -> new ArrayList<>()).add(dest);
        graph.computeIfAbsent(dest, x -> new ArrayList<>()).add(src);
    }

    // 재귀를 이용한 DFS
    public void dfsRecursive(int current, Set<Integer> visited) {
        visited.add(current);
        System.out.print(current + " ");

        for(int neighbor : graph.getOrDefault(current, new ArrayList<>())) {
            if(!visited.contains(neighbor)) {
                dfsRecursive(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        DFSRecursive dfsRec = new DFSRecursive();

        // 예제 데이터
        //         0
        //       /   \
        //      1     2
        //     / \   / \
        //    3   4 5   6
        dfsRec.addEdge(0, 1);
        dfsRec.addEdge(0, 2);
        dfsRec.addEdge(1, 3);
        dfsRec.addEdge(1, 4);
        dfsRec.addEdge(2, 5);
        dfsRec.addEdge(2, 6);

        // 출력: 0 1 3 4 2 5 6
        dfsRec.dfsRecursive(0, new HashSet<>());
    }
}

 

2-2. 스택 기반 DFS

import java.util.*;

public class DFSStack {
    // 그래프를 인접 리스트로 표현
    private Map<Integer, List<Integer>> graph;

    public DFSStack() {
        graph = new HashMap<>();
    }

    // 무방향 그래프에 간선 추가
    public void addEdge(int src, int dest) {
        graph.computeIfAbsent(src, x -> new ArrayList<>()).add(dest);
        graph.computeIfAbsent(dest, x -> new ArrayList<>()).add(src);
    }

    // 스택을 사용한 DFS 구현
    public void dfsStack(int start) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int current = stack.pop();
            if (!visited.contains(current)) {
                visited.add(current);
                System.out.print(current + " ");

                List<Integer> neighbors = graph.getOrDefault(current, new ArrayList<>());
                
                // 왼쪽 노드부터 탐색하기 위해 역순 정렬
                Collections.sort(neighbors, Collections.reverseOrder());
                for (int neighbor : neighbors) {
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }

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

        // 예제 데이터
        //         0
        //       /   \
        //      1     2
        //     / \   / \
        //    3   4 5   6
        dfs.addEdge(0, 1);
        dfs.addEdge(0, 2);
        dfs.addEdge(1, 3);
        dfs.addEdge(1, 4);
        dfs.addEdge(2, 5);
        dfs.addEdge(2, 6);

        // 출력: 0 1 3 4 2 5 6
        dfs.dfsStack(0);
    }
}