BFS의 동작 원리
BFS는 다음과 같은 절차를 따릅니다:
-
탐색을 시작할 노드를 큐(Queue)에 삽입하고 방문 처리를 합니다.
-
큐에서 노드를 꺼내어 해당 노드의 인접한(연결된) 노드들을 확인합니다.
-
아직 방문하지 않은 인접 노드를 모두 큐에 삽입하고 방문 처리를 합니다.
-
큐가 빌 때까지 2~3 과정을 반복합니다.
BFS는 FIFO(First In, First Out) 구조의 큐를 사용하기 때문에, 먼저 삽입된 노드를 먼저 처리하게 됩니다. 이를 통해 탐색이 깊어지기 전에 넓게 퍼지면서 진행됩니다.
BFS의 예제 코드 (Python)
from collections import deque
def bfs(graph, 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)
# 그래프 예제 (인접 리스트 표현)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'E': ['B', 'H'],
'F': ['C'],
'G': ['C'],
'H': ['E']
}
bfs(graph, 'A') # A부터 탐색 시작실행 결과
A B C D E F G H위 코드는 ‘A’ 노드부터 시작하여 인접한 노드를 먼저 탐색하는 모습을 보여줍니다.
BFS의 특징
-
최단 경로 보장: BFS는 모든 간선의 가중치가 동일할 때, 시작 노드에서 특정 노드까지의 최단 경로를 찾는 데 유용합니다.
-
완전 탐색 가능: BFS는 모든 노드를 방문하며, 연결된 모든 영역을 탐색하는 데 적합합니다.
-
메모리 사용량: 큐를 사용하기 때문에 노드가 많을 경우 메모리 사용량이 증가할 수 있습니다.
BFS와 DFS 비교
| 알고리즘 | 탐색 방식 | 자료구조 | 사용 사례 |
|---|---|---|---|
| BFS | 인접한 노드를 먼저 탐색 | 큐 (Queue) | 최단 경로 찾기, 네트워크 탐색 |
| DFS | 한 방향으로 끝까지 탐색 | 스택 (Stack) 또는 재귀 | 경로 탐색, 미로 찾기 |
BFS의 활용 사례
-
최단 경로 탐색: 네트워크에서 최단 거리 찾기 (예: Google Maps, 네트워크 라우팅)
-
웹 크롤러: 웹 페이지를 단계별로 탐색하여 정보를 수집하는데 사용
-
SNS 친구 추천: 특정 사용자의 가까운 관계를 먼저 탐색하여 친구 추천
-
미로 탐색: 출구까지의 최단 경로를 찾는 데 활용
결론
BFS는 그래프에서 너비를 우선적으로 탐색하는 알고리즘으로, 최단 경로 탐색 등에 자주 사용됩니다. 큐(Queue)를 활용하며, 노드를 넓게 탐색하는 특성이 있어 특정 문제 해결에 강력한 도구가 됩니다. DFS와의 차이점을 이해하고, 문제 유형에 맞게 BFS를 활용하면 효과적인 문제 해결이 가능합니다.