depth-first search(DFS)란 무엇인가요?

Question

Accepted Answer

**DFS**는 각 분기를 따라 가능한 한 깊이 들어간 뒤 backtrack(되돌아감)하는 방식으로 그래프를 탐색합니다. **stack(스택)**(흔히 재귀를 통한 call stack)을 사용하며 다른 대안을 탐색하기 전에 한 경로 전체를 방문합니다.

## 개념

한 노드에서 방문하지 않은 이웃으로 재귀하며 계속 깊이 들어가고, 막히면 되돌아가 다른 분기를 시도합니다.

## 예시

```python
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nbr in graph[node]:
        if nbr not in visited:
            order += dfs(graph, nbr, visited)  # 먼저 더 깊이 들어감
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
dfs(graph, 'A')                        # -> ['A', 'B', 'D', 'C']
```

## BFS와 DFS 비교

| | BFS | DFS |
|---|-----|-----|
| 구조 | queue | stack / 재귀 |
| 찾는 것 | 최단(가중치 없음) | 임의의 경로 |
| 메모리 | O(V) 프런티어 | O(깊이) |
| 적합한 곳 | 최단 경로, 레벨 | 사이클, 위상 정렬, 요소 |

## 복잡도

- **시간:** O(V + E). **공간:** O(V)(재귀 깊이 + visited).

## 함정

깊은 그래프는 재귀 스택을 오버플로할 수 있습니다 — 명시적 스택을 사용하세요. 사이클을 처리하려면 `visited`를 추적하세요.

## 왜 중요한가

DFS는 사이클 탐지, topological sort, 연결 요소, 미로/경로 생성을 뒷받침합니다.

재귀적 우아함이 트리와 그래프 코드를 간결하게 만듭니다.

언제 depth-first가 breadth-first보다 나은지 아는 것은 그래프 알고리즘 숙련도의 핵심입니다.

	BFS	DFS
구조	queue	stack / 재귀
찾는 것	최단(가중치 없음)	임의의 경로
메모리	O(V) 프런티어	O(깊이)
적합한 곳	최단 경로, 레벨	사이클, 위상 정렬, 요소