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

Stupefyee

Jun 10, 2025

Contents

1. 핵심 개념 2. DFS 기본 구조 (재귀 방식)3. DFS의 특징 4. DFS 활용 예시 5. DFS vs BFS 차이 6. DFS 구현 방법 정리

💡

그래프, 트리, 또는 탐색 공간에서 가능한 한 깊이까지 탐색한 후, 더 이상 진행이 불가능하면 다시 돌아가서 다른 경로를 탐색하는 방법

1. 핵심 개념

한 방향으로 깊이 들어감

갈 수 있는 곳까지 가본 뒤, 되돌아가서 다른 경로 탐색

재귀 또는 스택으로 구현 가능

2. DFS 기본 구조 (재귀 방식)


void dfs(Node node, boolean[] visited) {
    visited[node] = true;     // 현재 노드 방문 처리

    for (Node next : node.neighbors) {
        if (!visited[next]) {
            dfs(next, visited); // 다음 노드로 재귀 호출
        }
    }
}

3. DFS의 특징

항목	설명
탐색 방식	한 방향으로 계속 내려감
자료 구조	스택 또는 재귀 호출
백트래킹	돌아와서 다른 경로도 시도
시간 복잡도	O(V + E) (V: 정점 수, E: 간선 수)
사용 예시	경로 찾기, 퍼즐 탐색, 완전탐색 등

4. DFS 활용 예시

백트래킹 문제 (예: 순열, 조합, 최대 탐색)

미로 탐색

트리 구조 순회

모든 경우의 수 탐색

피로도 문제에서 최대 던전 탐험 수 찾기

5. DFS vs BFS 차이

항목	DFS	BFS
우선 순위	깊이 (Depth)	너비 (Breadth)
구조	스택 / 재귀	큐
경로	가능한 한 깊이까지 탐색	인접 노드부터 차례대로 탐색

6. DFS 구현 방법 정리

재귀 사용: 가장 직관적이고 간단

스택 사용: 명시적 스택으로 구현 가능

방문 배열: 중복 탐색 방지를 위해 사용

Contents

1. 핵심 개념 2. DFS 기본 구조 (재귀 방식)3. DFS의 특징 4. DFS 활용 예시 5. DFS vs BFS 차이 6. DFS 구현 방법 정리

기술정리

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

Stupefyee

Jun 10, 2025

Contents

1. 핵심 개념 2. DFS 기본 구조 (재귀 방식)3. DFS의 특징 4. DFS 활용 예시 5. DFS vs BFS 차이 6. DFS 구현 방법 정리

💡

그래프, 트리, 또는 탐색 공간에서 가능한 한 깊이까지 탐색한 후, 더 이상 진행이 불가능하면 다시 돌아가서 다른 경로를 탐색하는 방법

1. 핵심 개념

한 방향으로 깊이 들어감

갈 수 있는 곳까지 가본 뒤, 되돌아가서 다른 경로 탐색

재귀 또는 스택으로 구현 가능

2. DFS 기본 구조 (재귀 방식)


void dfs(Node node, boolean[] visited) {
    visited[node] = true;     // 현재 노드 방문 처리

    for (Node next : node.neighbors) {
        if (!visited[next]) {
            dfs(next, visited); // 다음 노드로 재귀 호출
        }
    }
}

3. DFS의 특징

항목	설명
탐색 방식	한 방향으로 계속 내려감
자료 구조	스택 또는 재귀 호출
백트래킹	돌아와서 다른 경로도 시도
시간 복잡도	O(V + E) (V: 정점 수, E: 간선 수)
사용 예시	경로 찾기, 퍼즐 탐색, 완전탐색 등

4. DFS 활용 예시

백트래킹 문제 (예: 순열, 조합, 최대 탐색)

미로 탐색

트리 구조 순회

모든 경우의 수 탐색

피로도 문제에서 최대 던전 탐험 수 찾기

5. DFS vs BFS 차이

항목	DFS	BFS
우선 순위	깊이 (Depth)	너비 (Breadth)
구조	스택 / 재귀	큐
경로	가능한 한 깊이까지 탐색	인접 노드부터 차례대로 탐색

6. DFS 구현 방법 정리

재귀 사용: 가장 직관적이고 간단

스택 사용: 명시적 스택으로 구현 가능

방문 배열: 중복 탐색 방지를 위해 사용

Contents

1. 핵심 개념 2. DFS 기본 구조 (재귀 방식)3. DFS의 특징 4. DFS 활용 예시 5. DFS vs BFS 차이 6. DFS 구현 방법 정리