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

 

DFS는 깊이 우선 탐색으로 그래프에서 특정 노드에서 시작하여 가장 깊은 노드까지 탐색한 후, 되돌아가며 다음 경로를 탐색하는 방식이다. 재귀나 스택을 사용해 구현할 수 있고, BFS와는 반대로 동작한다.

1. DFS의 특징
   1. 탐색 방식
   • 한 경로를 따라 깊이 탐색한 뒤, 더 이상 갈 곳이 없으면 이전 노드로 되돌아온다.
   • 모든 노드를 방문할 때까지 반복한다.
   2. 사용 자료구조
   • 재귀 호출(Stack Frame)
   • 명시적인 스택(Stack)
   3. 시간 복잡도
   • O(V + E), V: 정점의 수, E: 간선의 수
   4. 용도
   • 사이클 탐지
   • 모든 경로 탐색
   • 연결 요소 탐색
   • 백트래킹 기반 문제 해결
2. DFS의 동작 과정
   1. 시작 노드 방문
   • 시작 노드를 방문하고 처리(출력, 기록 등)한다.
   2. 인접 노드 탐색
   • 방문하지 않은 인접 노드가 있으면 해당 노드를 방문한다.
   3. 백트래킹
   • 더 이상 방문할 노드가 없으면 이전 노드로 되돌아간다.
   4. 반복
   • 모든 노드를 방문할 때까지 1~3번을 반복한다.

재귀 방식

import java.util.Arrays;  
import java.util.List;  

public class DFSRecursive {  
    public static void dfs(int node, boolean[] visited, List<List<Integer>> graph){  
        // 현재 노드 방문  
        visited[node] = true;  
        System.out.println("Visited node: " + node);  

        // 인접 노드 탐색  
        for(int neighbor : graph.get(node)){  
            if(!visited[neighbor]){  
                dfs(neighbor, visited, graph); // 재귀 호출  
            }  
        }  
    }  

    public static void main(String[] args) {  
        // 그래프 정의(인접 리스트)  
        List<List<Integer>> graph = Arrays.asList(  
                Arrays.asList(1, 2),    // 0번 노드의 인접 노드  
                Arrays.asList(0, 3),    // 1번 노드의 인접 노드  
                Arrays.asList(0, 4),    // 2번 노드의 인접 노드  
                Arrays.asList(1),       // 3번 노드의 인접 노드  
                Arrays.asList(2)        // 4번 노드의 인접 노드  
        );  

        boolean[] visited = new boolean[graph.size()];  
        dfs(0, visited, graph); // 0번 노드에서 탐색 시작  
    }  
}

    0
   / \
  1   2
   \   \
    3   4

Visited node: 0
Visited node: 1
Visited node: 3
Visited node: 2
Visited node: 4

스택 방식

import java.util.Arrays;  
import java.util.List;  
import java.util.Stack;  

public class DFSIterative {  
    public static void dfsIterative(int start, List<List<Integer>> graph){  
        boolean[] visited = new boolean[graph.size()];  
        Stack<Integer> stack = new Stack<>();  

        stack.push(start); // 시작 노드를 스택에 추가  

        while(!stack.isEmpty()){  
            int node = stack.pop();  

            if(!visited[node]){  
                visited[node] = true; // 방문 처리  
                System.out.println("Visited node: " + node);  

                // 스택에 인접 노드 추가(거꾸로 추가하면 방문 순서 조정 가능)  
                for(int neighbor : graph.get(node)){  
                    if(!visited[neighbor]){  
                        stack.push(neighbor);  
                    }  
                }  
            }  
        }  
    }  

    public static void main(String[] args) {  
        // 그래프 정의(인접 리스트)  
        List<List<Integer>> graph = Arrays.asList(  
                Arrays.asList(1, 2),    // 0번 노드의 인접 노드  
                Arrays.asList(0, 3),    // 1번 노드의 인접 노드  
                Arrays.asList(0, 4),    // 2번 노드의 인접 노드  
                Arrays.asList(1),       // 3번 노드의 인접 노드  
                Arrays.asList(2)        // 4번 노드의 인접 노드  
        );

        dfsIterative(0, graph); // 0번 노드에서 탐색 시작  
    }  
}

Visited node: 0
Visited node: 2
Visited node: 4
Visited node: 1
Visited node: 3

List<List<Integer>> graph = Arrays.asList(  
        Arrays.asList(1, 2),    // 0번 노드의 인접 노드  
        Arrays.asList(0, 3),    // 1번 노드의 인접 노드  
        Arrays.asList(0, 4),    // 2번 노드의 인접 노드  
        Arrays.asList(1),       // 3번 노드의 인접 노드  
        Arrays.asList(2)        // 4번 노드의 인접 노드  
);

넣는 순서대로 0, 1, 2번 노드이다.
0번 노드는 1, 2 2개이다.
graph.get(node)로 뽑으면 node가 0일 때 1, 2가 나온다.

node가 1이면 0, 3이 나온다.

for(int neighbor : graph.get(node)){  
    if(!visited[neighbor]){  
        stack.push(neighbor);  
    }  
}  

node가 0일 때 반복문에서 stack에 1, 2 순서로 저장된다.

int node = stack.pop();

stack.pop은 후입선출이기에 2부터 검색한다.

node가 2이면 list는 0, 4를 뽑고

stack.push(neighbor);

0은 이미 방문한 노드이기에 4를 stack에 추가한다.
node 4는 인접 노드가 2이고 2는 이미 방문했기에 로직을 종료한다.

while(!stack.isEmpty()){

stack에 1이 들어 있기에 해당 로직을 진행한다.

인접 노드

인접 노드는 노드의 옆에 있는 노드를 가리킨다.
1개일 수도, 여러 개일 수도 있다.

3. DFS와 BFS의 비교

특징	BFS	DFS
탐색 방식	너비 우선 탐색(레벨별 탐색)	깊이 우선 탐색(한 경로를 끝까지 탐색)
자료구조	큐(FIFO 사용)	스택(재귀 호출 또는 명시적 스택 사용)
최단 경로	가중치 없는 그래프에서 최단 경로 보장	일반적으로 최적화되지 않음
사용 예	최단 경로 탐색, 레벨별 탐색	모든 경로 탐색, 백트래킹 문제 해결
메모리 사용량	더 많음(큐에 모든 레벨 저장)	더 적음(스택 깊이만큼 사용)

DFS의 재귀 방식은 내부적으로 스택을 사용(암시적 사용)한다.

4. DFS의 활용 사례
   1. 사이클 탐지
   • 그래프에서 사이클이 있는지 확인
   2. 모든 경로 탐색
   • 출발지에서 목적지까지의 모든 가능한 경로를 탐색
   • 예: 미로에서 모든 출구 찾기
   3. 백트래킹 문제 해결
   • DFS를 기반으로 탐색 중 조건을 만족하지 않으면 돌아가는 방식
   • 예: N-Queens, Sudoku
   4. 연결 요소 탐색
   • 비연결 그래프에서 연결된 컴포넌트를 탐색
   5. 위상 정렬
   • DAG(Directed Acyclic Graph)에서 순서를 정하는데 사용
   6. 강결합 컴포넌트(SCC)
   • 그래프의 강결합된 부분 집합을 탐지

5. 백트래킹
   DFS는 백트래킹(Backtracking) 알고리즘의 기본이다. 백트래킹은 특정 조건에서 탐색을 중단하고 되돌아가는 방식으로 동작한다. N-Queens 문제는 DFS와 백트래킹을 결합해 해결한다.