breadth-first search(BFS)란 무엇인가요?

Question

Accepted Answer

**BFS**는 그래프를 레벨 단위로 탐색하여, 더 깊이 들어가기 전에 한 노드의 모든 이웃을 방문합니다. **queue(큐)**를 사용하며 가중치 없는 그래프에서 **최단 경로**(가장 적은 간선 수)를 찾습니다.

## 개념

시작점에서 출발하여 그것을 큐에 넣고, 반복적으로 노드를 큐에서 꺼내 방문하지 않은 이웃을 방문하고 큐에 넣습니다. `visited` 셋이 재방문을 방지합니다.

## 예시

```python
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()        # FIFO: 가장 가까운 것부터 탐색
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                queue.append(nbr)
    return order

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

## 복잡도

- **시간:** O(V + E) — 각 정점과 간선을 한 번씩.
- **공간:** 큐와 visited 셋을 위한 O(V).

## 언제 사용하나 / 함정

**가중치 없는 그래프의 최단 경로**, 레벨 순서 순회, 연결 요소 찾기에 BFS를 사용하세요. DFS보다 메모리를 더 많이 사용합니다(한 번에 전체 프런티어를 유지). 항상 `visited`를 추적하세요. 그렇지 않으면 사이클에서 영원히 반복할 수 있습니다.

## 왜 중요한가

BFS는 모든 간선이 동일하게 중요할 때의 최단 경로를 위한 *바로 그* 알고리즘입니다 — 라우팅, 웹 크롤링, 소셜 네트워크의 분리 단계.

큐 기반의 레벨 단위 구조는 근본적인 순회 패턴입니다.

BFS와 DFS를 구별할 줄 알면 도달 가능성, 경로, 순서 문제에 올바른 도구를 고를 수 있습니다.