[알고리즘] 탐색 알고리즘 기본적인 이해와 구현 - 6. 깊이 우선 탐색

1. 선형 탐색 (Linear Search)
2. 이진 탐색 (Binary Search)
3. 점프 탐색 (Jump Search)
4. 보간 탐색 (Interpolation Search)
5. 지수 탐색 (Exponential Search)
6. 깊이 우선 탐색 (Depth-First Search, DFS)
7. 너비 우선 탐색 (Breadth-First Search, BFS)

 

 

깊이 우선 탐색

깊이 우선 탐색은 트리나 그래프에서 출발 노드에서 시작하여 최대한 깊이 탐색한 뒤, 더 이상 갈 수 없는 노드로부터 거슬러 올라와 탐색을 이어가는 방식입니다. DFS는 순환 구조(재귀)나 명시적 스택을 사용하여 구현할 수 있습니다. DFS는 그래프에서 경로를 찾거나 사이클 여부를 확인하는 데 유용하게 사용됩니다.

 

1. 특징

• 깊이 우선: 이름처럼 한 경로를 따라 최대한 깊이 이동하다가, 더 이상 탐색할 노드가 없을 때 이전 노드로 되돌아옵니다.
• 재귀적 구현 가능: DFS는 재귀적 특성을 가지며, 재귀 호출을 통해 간단히 구현할 수 있습니다. (비재귀적 구현 시 스택을 사용)
• 비순환 그래프에서 사이클 탐지에 유용: DFS는 그래프의 사이클을 감지하거나 특정 경로가 존재하는지 탐색할 때 많이 사용됩니다.

 

2. 복잡도

• 시간 복잡도: O(V+E)O(V + E)O(V+E), 여기서 VVV는 노드(정점)의 개수, EEE는 간선의 개수입니다.
• 공간 복잡도: 재귀 호출이나 스택에 의해 O(V)O(V)O(V)의 추가 공간을 사용합니다.

 

3. 예제

import java.util.*;

public class DFSExample {
    private static void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
        visited[node] = true;
        System.out.print(node + " ");

        // 현재 노드와 연결된 모든 노드를 방문
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited, graph);
            }
        }
    }

    public static void main(String[] args) {
        int n = 5; // 노드 개수
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 그래프 연결 (양방향)
        graph.get(0).add(1);
        graph.get(0).add(2);
        graph.get(1).add(3);
        graph.get(1).add(4);

        boolean[] visited = new boolean[n];
        System.out.println("DFS 시작:");
        dfs(0, visited, graph);
    }
}

• 위 코드에서 DFS 탐색이 시작되면, 주어진 노드와 연결된 노드들이 순차적으로 깊이 탐색됩니다.

 

4. 주 사용처

• 경로 탐색 및 사이클 검출: 특정 노드 간의 경로 존재 여부나 사이클 존재 여부를 판별하는 데 적합합니다.
• 그래프 구성 요소 연결성 검사: 연결된 구성 요소를 식별하거나 특정 영역을 탐색하는 데 자주 활용됩니다.
• 문제 해결 알고리즘: 백트래킹, 미로 탐색, 퍼즐 문제 해결과 같은 깊이 탐색이 요구되는 문제에서 사용됩니다.

 

감사합니다.