DFS

DFS(Depth-First Search, 깊이 우선 탐색) 알고리즘

 

DFS는 그래프나 트리에서 깊이 우선으로 노드를 탐색하는 방법입니다. DFS는 한 번에 가능한 한 깊이 내려가다가 더 이상 내려갈 곳이 없으면 이전 단계로 돌아가서 다른 경로를 탐색하는 방식입니다. DFS는 트리나 그래프의 구조를 탐색할 때 유용하며, 경로 탐색, 미로 찾기, 사이클 탐지 등의 문제에서 활용될 수 있습니다.

DFS 동작 방식:
1. 시작 노드에서 시작하여, 그 노드와 연결된 노드들을 깊이 우선으로 탐색합니다.
2. 방문한 노드는 다시 방문하지 않도록 표시합니다.
3. 더 이상 방문할 노드가 없으면, 이전 노드로 돌아가서 탐색을 계속합니다.
4. 모든 노드를 탐색할 때까지 이 과정을 반복합니다.

DFS의 특징:
- 시간 복잡도: 그래프의 모든 노드와 간선을 한 번씩만 처리하므로 O(V + E)입니다. 여기서 V는 노드의 수, E는 간선의 수입니다.
- 공간 복잡도: 스택을 사용하는 경우 O(V)만큼의 공간이 필요합니다. (재귀 방식의 경우 함수 호출 스택에 의해 발생)

 

DFS는 트리나 그래프의 구조를 탐색할 때 유용하며, 경로 탐색, 미로 찾기, 사이클 탐지 등의 문제에서 활용될 수 있습니다.

DFS 구현 (자바)
DFS는 스택을 이용한 비재귀 방식과 재귀 방식을 모두 구현할 수 있습니다. 여기서는 재귀 방식과 비재귀 방식을 모두 설명하겠습니다.

1. 그래프 표현
우리는 그래프를 인접 리스트 방식으로 표현합니다. 인접 리스트는 각 노드에 대해 연결된 노드들의 리스트를 저장하는 방식입니다.

import java.util.*;

public class DFSExample {
    private static Map<Integer, List<Integer>> graph = new HashMap<>();
    
    // 그래프에 간선 추가
    public static void addEdge(int v, int w) {
        graph.putIfAbsent(v, new ArrayList<>());
        graph.get(v).add(w);
    }
    
    // DFS - 재귀 방식
    public static void dfsRecursive(int start, Set<Integer> visited) {
        // 현재 노드를 방문했다고 표시
        visited.add(start);
        System.out.print(start + " ");  // 현재 노드 출력
        
        // 현재 노드와 연결된 모든 노드를 재귀적으로 방문
        for (int neighbor : graph.getOrDefault(start, Collections.emptyList())) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(neighbor, visited);
            }
        }
    }

    // DFS - 비재귀 방식 (스택 이용)
    public static void dfsIterative(int start) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited.contains(node)) {
                visited.add(node);
                System.out.print(node + " ");  // 현재 노드 출력
                
                // 현재 노드와 연결된 모든 노드를 스택에 넣음
                List<Integer> neighbors = graph.getOrDefault(node, Collections.emptyList());
                for (int neighbor : neighbors) {
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) {
        // 간선 추가 (그래프 생성)
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
        addEdge(3, 6);
        
        System.out.println("DFS (재귀):");
        Set<Integer> visited = new HashSet<>();
        dfsRecursive(1, visited);  // 시작 노드 1에서 DFS
        
        System.out.println("\nDFS (비재귀):");
        dfsIterative(1);  // 시작 노드 1에서 DFS
    }
}

설명:
1. addEdge: `v`와 `w`를 연결하는 간선을 추가합니다.
2. dfsRecursive: 시작 노드에서 깊이 우선 탐색을 재귀적으로 수행합니다.
3. dfsIterative: 스택을 이용하여 깊이 우선 탐색을 비재귀적으로 수행합니다.
4. main: 그래프를 구성하고, 두 가지 방식으로 DFS를 실행하여 결과를 출력합니다.

출력 예시:

DFS (재귀):
1 2 4 5 3 6

DFS (비재귀):
1 2 4 5 3 6

위 코드에서는 시작 노드인 1을 기준으로 DFS 탐색을 진행합니다. 재귀 방식과 비재귀 방식에서 동일한 결과를 얻을 수 있습니다.

재귀와 비재귀의 차이:
- 재귀: 함수 호출 스택을 사용하므로 코드가 간결하지만, 큰 그래프에서 스택 오버플로우가 발생할 수 있습니다.
- 비재귀: 명시적인 스택을 사용하므로, 재귀에 비해 메모리 관리가 좀 더 명확하지만 코드가 다소 복잡할 수 있습니다.