5. 깊이 우선 탐색 (DFS, Depth-First Search) — 스택/재귀

핵심 인사이트 (3줄 요약)

1. 본질: DFS (Depth-First Search)는 한 방향으로 갈 수 있는 끝까지 파고든 뒤 역추적 (Backtracking)하여 다른 경로를 탐색하는 그래프/트리 탐색 알고리즘이다.
2. 가치: 재귀 또는 스택으로 구현이 간단하고 O(V+E) 시간에 위상 정렬 (Topological Sort), 강연결 요소 (SCC), 사이클 검출, 미로 탈출 등 다양한 문제를 해결한다.
3. 판단 포인트: 최단 경로에는 BFS를, 전체 경로 탐색·위상 정렬·SCC에는 DFS를 선택하며, 재귀 깊이가 깊으면 스택 오버플로우에 주의한다.

Ⅰ. 개요 및 필요성

깊이 우선 탐색 (DFS, Depth-First Search)은 그래프의 한 정점에서 출발해 인접 정점을 방문할 때 가능한 한 깊게 들어가고, 더 이상 갈 곳이 없으면 역추적하여 탐색하지 않은 다른 경로를 탐색하는 방법이다.

DFS가 필요한 상황:

• 위상 정렬 (Topological Sort): DAG에서 작업 순서 결정
• 강연결 요소 (SCC, Strongly Connected Components) 탐색
• 사이클 검출 (Cycle Detection)
• 미로 탈출, 퍼즐 풀이, 백트래킹 기반 탐색
• DFS 트리의 간선 분류 (트리 간선, 역방향 간선)

📢 섹션 요약 비유: DFS는 미로에서 오른손을 벽에 대고 계속 따라가는 방법이다. 막다른 골목이면 왔던 길로 돌아가 다른 방향을 시도한다.

Ⅱ. 아키텍처 및 핵심 원리

기본 동작 순서

그래프:  A — B — D
         |       |
         C ———— E

DFS 시작: A

방문 순서:
  A 방문 → B 탐색
  B 방문 → D 탐색
  D 방문 → E 탐색
  E 방문 → C 탐색
  C 방문 → 이미 방문한 A만 남음 → 역추적
  최종: A → B → D → E → C

ASCII 다이어그램 — DFS 스택 진행

┌────────────────────────────────────────────────────────┐
│  그래프:  A ─ B ─ D       DFS 스택 변화:               │
│           │       │                                    │
│           C ───── E       초기:    [A]                 │
│                           A 팝:    [] → 방문A → [C, B]  │
│  탐색 순서:                B 팝:    [C] → 방문B → [C, D] │
│  A → B → D → E → C       D 팝:    [C] → 방문D → [C, E] │
│                           E 팝:    [C] → 방문E → [C]    │
│  방문: ✓ A ✓ B ✓ D        C 팝:    [] → 방문C → []       │
│        ✓ E ✓ C            완료!                         │
└────────────────────────────────────────────────────────┘

DFS 간선 분류 (방향 그래프)

DFS 수행 중 발견되는 간선의 종류:

역방향 간선 (Back Edge) 존재 = 사이클 존재

DFS 방문 시간 (Discovery/Finish Time)

각 정점에 발견 시간 d[v]와 완료 시간 f[v]를 기록
→ 위상 정렬: f[v] 내림차순 = 위상 정렬 순서
→ SCC: f[v]를 이용해 강연결 요소 식별 (코사라주 알고리즘)

📢 섹션 요약 비유: DFS의 역방향 간선은 조상의 발을 다시 밟는 것과 같다. 조상을 다시 밟으면 사이클이 있다는 증거다.

Ⅲ. 비교 및 연결

DFS vs BFS

📢 섹션 요약 비유: DFS는 한 우물을 끝까지 파는 광부, BFS는 지층별로 수평으로 넓게 파는 광부다. 금이 깊이 있으면 DFS, 가장 가까운 금을 찾으려면 BFS다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오

시나리오 1: 의존성 분석 (빌드 시스템)

• Maven, Gradle의 빌드 의존성 그래프에서 사이클 검출
• DFS로 역방향 간선 탐색 → "순환 의존성 오류" 보고

시나리오 2: 미로 알고리즘 / 게임 AI

• DFS + 백트래킹으로 목적지까지 가능한 경로 탐색
• 체스 엔진: 가능한 수 깊이 탐색 (게임 트리 DFS)

시나리오 3: 파일 시스템 순회

• 디렉토리 트리는 사실상 DFS 순회
• find 명령어, IDE 파일 인덱싱 모두 DFS 기반

시나리오 4: 스택 오버플로우 방지

• 재귀 DFS에서 그래프 깊이가 10만 이상이면 시스템 콜 스택 오버플로우
• 해결: 명시적 스택 (Explicit Stack) 또는 반복 DFS 구현

기술사 판단 포인트

📢 섹션 요약 비유: DFS는 건물 배관 검사처럼 한 파이프를 끝까지 따라가다가 막히면 분기점으로 돌아오는 방식이다. 가장 깊은 문제를 찾는 데 탁월하지만 "제일 가까운 문제"를 찾는 데는 맞지 않는다.

Ⅴ. 기대효과 및 결론

DFS (Depth-First Search)는 O(V+E)의 효율로 사이클 검출, 위상 정렬, SCC 분해 등 그래프 분석의 핵심 연산을 수행한다. 재귀로 구현이 우아하지만 깊은 그래프에서는 명시적 스택을 사용하여 스택 오버플로우를 방지해야 한다.

핵심 결론: DFS는 "끝까지 파고드는 분석"의 알고리즘이다. 경로 존재 여부, 사이클, 위상 순서 모두 DFS 한 번으로 해결할 수 있다.

📢 섹션 요약 비유: DFS는 소설을 처음부터 끝장까지 한 챕터씩 읽는 것과 같다. 중간에 끝이 막히면 이전 챕터로 돌아가 다른 가지를 탐색한다. 반면 BFS는 모든 챕터의 첫 페이지를 먼저 읽고 두 번째 페이지를 읽는 것이다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[BFS (Breadth-First Search)]
    │
    ▼
[위상 정렬 (Topological Sort)]
    │
    ▼
[SCC (Strongly Connected Components)]
    │
    ▼
[백트래킹 (Backtracking)]
    │
    ▼
[사이클 검출 (Cycle Detection)]

이 흐름도는 BFS (Breadth-First Search)에서 출발해 사이클 검출 (Cycle Detection)까지 이어지며, 중간 단계가 기초 개념을 실무 구조로 발전시키는 과정을 보여준다.

👶 어린이를 위한 3줄 비유 설명

1. 🌳 DFS는 나무 타기처럼 제일 높은 가지까지 올라갔다가 내려와서 다른 가지로 옮기는 방식이다.
2. 🧩 미로에서 오른손을 벽에 붙이고 계속 걸어가면 결국 출구를 찾게 되는 것처럼, DFS도 막힐 때까지 직진하다가 돌아온다.
3. 📚 가장 먼저 찾은 경로가 꼭 가장 짧은 경로는 아니다 — 미로에서 돌아가는 길을 찾을 수도 있다.