[100일의 IT 초보 탈출] #51 BFS(너비 우선 탐색) _ 넓게 퍼지며 찾아가는 길

오늘은 무엇을 배우게 될까요?

 

지난 시간에는 DFS(깊이 우선 탐색)으로

데이터 구조 안에서 가장 깊은 곳부터 탐색하는 방식을 배웠습니다.

 

오늘은 그 반대 개념인 BFS(너비 우선 탐색)을 배워봅니다.

이 알고리즘은 최단 거리 탐색, 그래프 탐색, 게임 AI, 네트워크 탐색 등에 자주 쓰이며,

실제로 큐 자료구조가 어떻게 알고리즘에 활용되는지 보여주는 대표 사례입니다.

 

---

 

BFS란?

 

Breadth-First Search (너비 우선 탐색)은

시작 정점에서 가까운 노드부터 차례대로 탐색해 나가는 알고리즘입니다.

 

→ 한 노드에서 갈 수 있는 모든 이웃 노드를 먼저 탐색한 뒤, 그 다음 이웃의 이웃 노드를 탐색합니다.

 

→ 큐(Queue)를 사용해 탐색 순서를 관리합니다.

 

---

 

동작 원리 요약

 

1. 시작 노드를 큐에 넣고 방문 표시
2. 큐에서 노드를 꺼내고, 그 노드와 연결된 아직 방문하지 않은 이웃 노드를 큐에 넣음
3. 큐가 빌 때까지 위 과정을 반복

 

---

 

 

예시 그래프

A
├── B
│   └── D
└── C
    └── E

BFS 순서: A → B → C → D → E

 

---

 

 

DFS vs BFS 비교

항목DFS (깊이 우선)BFS (너비 우선)

자료구조	스택 or 재귀	큐
방문 순서	깊이 우선	가까운 노드 우선
사용 목적	경로 추적, 완전탐색	최단 경로, 거리 계산
구현 복잡도	간단 (재귀)	큐 활용 필요

 

---

BFS 실생활 비유

 

• SNS 친구 추천:
• 내 친구 → 친구의 친구 → 친구의 친구의 친구 순으로 확장
• 미로 찾기에서 가장 빠른 길
• 레벨 순회(트리):
• 부모 → 자식 → 손자 노드 순

 

---

 

 

Python 코드 (BFS)

from collections import deque

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': [],
    'E': []
}

def bfs(start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

bfs('A')

 

출력 결과

A B C D E

 

---

 

 

시간 복잡도

 

• 노드 수 V, 간선 수 E일 때
• → O(V + E)

 

---

 

 

BFS가 잘 쓰이는 예시

분야설명

미로 탐색	가장 빠른 길 찾기 (최단 경로)
네트워크 탐색	가까운 노드부터 단계별 연결
퍼즐 풀이	BFS 기반 상태 트리 탐색
AI 시스템	상황을 넓게 살펴보며 선택
트리 탐색	레벨 순회(Level Order Traversal)

 

---

 

주의할 점

 

• 큐에 넣는 순간 방문 표시를 해야 중복 탐색 방지 가능
• DFS보다 메모리 사용량이 많을 수 있음 (넓게 퍼지므로)
• 가중치가 있는 최단 경로 문제는 Dijkstra, A* 등을 써야 함

 

---

한 줄 요약

 

👉 BFS는 가까운 노드부터 탐색하는 큐 기반 알고리즘으로,

최단 경로 찾기와 레벨 순회 문제에서 강력한 성능을 보입니다.