[Daily morning study] BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)의 차이점 및 활용
in Daily morning study / DSA
#daily morning study
BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)의 차이점 및 활용
1. 개요
그래프 탐색 알고리즘은 주어진 그래프의 노드를 탐색하는 방법을 제공합니다. 두 가지 주요한 방법인 BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)는 각기 다른 방식으로 그래프를 탐색합니다. 이 가이드에서는 BFS와 DFS의 차이점, 각 방법의 활용에 대해 알아보겠습니다.
2. BFS(너비 우선 탐색)
2.1 정의
BFS는 그래프의 모든 노드를 탐색하기 위해 가장 가까운 노드부터 차례로 방문하는 방법입니다. 주로 큐(Queue)를 사용하여 현재 노드를 방문하고 그 노드의 인접 노드를 큐에 추가하는 방식으로 진행됩니다.
2.2 동작 원리
- 시작 노드를 큐에 삽입하고 방문 처리합니다.
- 큐에서 노드를 꺼내, 해당 노드의 모든 인접 노드를 큐에 추가합니다.
- 비어있는 큐에 대해서 이 과정을 반복합니다.
2.3 코드 예시
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
print(vertex, end=" ")
queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)
# 예제 그래프
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A')
3. DFS(깊이 우선 탐색)
3.1 정의
DFS는 가능한 깊이 들어가면서 노드를 탐색하다가 더 이상 방문할 노드가 없으면 되돌아오는 방식입니다. 보통 스택(Stack) 또는 재귀(Recursion)를 사용하여 구현됩니다.
3.2 동작 원리
- 시작 노드를 스택에 삽입하고 방문 처리합니다.
- 스택의 가장 위에 있는 노드를 꺼내, 해당 노드의 모든 인접 노드를 스택에 추가합니다.
- 비어 있는 스택에 대해서 이 과정을 반복합니다.
3.3 코드 예시
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=" ")
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# 예제 그래프
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
dfs(graph, 'A')
4. BFS와 DFS의 차이점
| 특징 | BFS | DFS |
|---|---|---|
| 데이터 구조 | 큐(Queue) | 스택(Stack) 또는 재귀 |
| 탐색 방식 | 최단 경로 탐색 가능 | 깊이 우선 탐색 |
| 방문 순서 | 레벨 순서로 방문 | 깊이 우선으로 방문 |
| 메모리 사용 | O(V) (V: 노드 수) | O(V) (재귀 깊이에 따라 최대 O(V)까지) |
| 복잡도 | O(V + E) | O(V + E) |
| 활용 예제 | 최단 경로 검색, 레벨 순서 탐색 | 경로 찾기, 토폴로지 정렬 등 |
5. 활용
5.1 BFS 활용
- 최단 경로 탐색: 가중치가 같은 그래프에서 최단 경로를 찾는 데 효과적입니다.
- 레벨 순서 탐색: 트리의 노드를 레벨별로 탐색할 때 사용합니다.
- 웹 크롤러: 페이지를 레벨 순서로 크롤링하기 위해 BFS를 사용합니다.
5.2 DFS 활용
- 미로 찾기: 깊이 우선으로 경로를 탐색하여 모든 가능한 경로를 확인할 수 있습니다.
- 토폴로지 정렬: DAG(Directed Acyclic Graph)에서의 작업 순서를 정할 때 사용합니다.
- 그래프의 연결 요소 찾기: 연결 그래프에서 모든 연결 요소를 탐색하는 데 유용합니다.
6. 결론
BFS와 DFS는 각기 다른 접근 방식을 지닌 그래프 탐색 알고리즘입니다. 문제에 따라 적절한 방법을 선택하는 것이 중요하며, 이해한 내용을 바탕으로 다양한 문제를 해결할 수 있습니다. 각 알고리즘의 특징과 활용도를 잘 기억해 두면 실제 개발 시 유용하게 사용할 수 있을 것입니다.
