DFS 개념

DFS (Depth-First Search) 개념

• DFS(Depth-First Search, 깊이 우선 탐색)는 그래프나 트리의 모든 노드를 탐색하는 알고리즘이다.
• 이 알고리즘은 한 노드에서 시작하여 가능한 깊이까지 탐색한 후 더 이상 탐색할 노드가 없으면 마지막으로 방문한 노드에서 다시 탐색을 시작한다.

 

 

DFS의 특징

• 경로 탐색: 한 경로를 가능한 깊이까지 탐색한다.
• 스택 기반: 재귀 호출이나 명시적인 스택을 사용하여 구현된다.
• 백트래킹: 더 이상 진행할 수 없는 경로를 만날 경우 이전 경로로 돌아가서 다른 경로를 탐색한다.

 

 

DFS의 장점

• 문제를 해결하기 위해 깊이 있는 경로를 탐색할 때 유용하다.
• 모든 노드를 메모리에 저장하지 않아도 되기 때문에 특정 상황에서는 메모리 사용이 적다.

 

 

DFS의 단점

• 순환이 있는 그래프에서는 무한 루프에 빠질 수 있다. 이를 방지하기 위해 방문한 노드를 추적해야 한다.
• 가장 짧은 경로를 찾는 데는 적합하지 않다.

 

 

자바에서의 DFS 구현 예제

 

1) 재귀를 사용한 DFS

트리나 그래프의 깊이 우선 탐색을 자연스럽게 표현한다.

import java.util.*;

public class DFSExample {
    static StringBuilder sb = new StringBuilder();  // 방문 순서를 저장할 StringBuilder
    static boolean[][] node;                        // 인접 행렬을 저장할 배열
    static boolean[] visited;                      // 방문 여부를 저장할 배열

    // DFS 함수
    static void dfs(int v) {
        if (visited[v]) 
            return;  // 이미 방문한 노드면 탐색 종료
        
        visited[v] = true;  // 현재 노드를 방문 처리
        sb.append(v + " "); // 방문한 노드를 StringBuilder에 추가
        
        // 현재 노드와 연결된 모든 노드를 재귀적으로 방문
        for (int i = 1; i < node[v].length; i++) {
            if (node[v][i] && !visited[i]) {
                dfs(i);
            }
        }
    }

    public static void main(String[] args) {
        int n = 5;  // 그래프의 노드 수
        
        // 인접 행렬 및 방문 배열 초기화
        node = new boolean[n + 1][n + 1];
        visited = new boolean[n + 1];
        
        // 그래프의 간선 설정 (예시)
        node[1][2] = node[2][1] = true;
        node[1][3] = node[3][1] = true;
        node[2][4] = node[4][2] = true;
        node[2][5] = node[5][2] = true;

        // DFS 탐색 시작 (시작 노드: 1)
        dfs(1);
        
        // 방문 순서 출력
        System.out.println("DFS 방문 순서: " + sb.toString().trim()); // 방문 순서: 1 2 4 5 3
    }
}

 

 

그래프 구조

1 - 2
|   |
3   4
    |
    5

 

• 재귀를 사용하면 DFS를 구현할 때 자연스럽게 깊이 탐색을 할 수 있다.
• 함수가 자기 자신을 호출하는 방식으로 그래프의 깊은 부분까지 탐색한다.

 

작동 방식

1. 현재 노드를 방문하고 결과를 저장한다.
2. 현재 노드와 연결된 모든 노드 중 방문하지 않은 노드가 있으면, 그 노드를 방문하기 위해 함수 자신을 호출한다.
3. 모든 연결된 노드를 탐색할 때까지 이 과정을 반복한다.

 

 

2) 스택을 사용한 DFS

재귀를 사용하지 않고 스택을 사용하여 DFS를 수행한다.

import java.util.*;

public class DFSExample {
    public static String dfs(int v, boolean node[][]) {
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        boolean visited[] = new boolean[node.length];  // 방문 여부 체크 배열
        stack.add(v);  // 시작 노드 추가
        
        while (!stack.isEmpty()) {
            int idx = stack.pop();  // 스택에서 노드를 꺼냄
            
            if (visited[idx])  // 이미 방문한 경우 생략
                continue;
            
            visited[idx] = true;  // 현재 노드 방문 처리
            sb.append(idx + " ");  // 방문한 노드 기록
            
            // 인접 노드 탐색
            for (int i = node.length - 1; i >= 0; i--) {
                if (node[idx][i] && !visited[i]) {
                    stack.add(i);  // 방문하지 않은 연결 노드를 스택에 추가
                }
            }
        }
        
        return sb.toString();
    }

    public static void main(String[] args) {
        int n = 5;  // 노드 수
        boolean[][] node = new boolean[n + 1][n + 1];

        // 그래프 간선 연결 설정 (예시)
        node[1][2] = node[2][1] = true;
        node[1][3] = node[3][1] = true;
        node[2][4] = node[4][2] = true;
        node[2][5] = node[5][2] = true;

        // DFS 실행 및 출력
        System.out.println(dfs(1, node));
    }
}

 

• 스택을 사용하면 DFS를 명시적으로 구현할 수 있다.
• 스택은 마지막에 추가된 요소부터 제거되기 때문에 스택의 구조를 통해 깊이 우선 탐색을 한다.

 

작동 방식

1. 시작 노드를 스택에 추가한다.
2. 스택에서 노드를 꺼내어 방문한다.
3. 꺼낸 노드의 인접 노드 중 방문하지 않은 노드를 스택에 추가한다.
4. 스택이 비어 있을 때까지 이 과정을 반복한다.