[알고리즘] DFS와 BFS

DFS와 BFS

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프 탐색 알고리즘으로, 각각 다른 방식으로 노드를 탐색하면서 그래프의 모든 노드를 방문하는데 사용된다. 각각의 특징과 장단점을 살펴보자.

 

https://namu.wiki/w/BFS

 

시간복잡도

• 두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.
• DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합한다.

 

	DFS	BFS
장점	메모리 사용이 상대적으로 적다. 스택을 사용하므로 각 노드를 방문하기 위해 추가 메모리가 거의 필요하지 않다. 경로가 길 경우 BFS보다 빠르게 해답을 찾을 수 있다. 일반적으로 재귀 구조로 구현하기 쉽다.	최단 경로를 보장한다. 무한루프에 빠질 위험이 적다. 사이클이 있는 그래프라도 노드를 중복 방문하지 않기 때문이다. 일반적으로 반복 구조로 구현하기 쉽다.
단점	최단 경로를 보장하지 않는다. 따라서 최단 경로 문제에 적합하지 않을 수 있다. 무한루프에 빠질 위험이 있다. 사이클이 있는 그래프에서 무한히 순환할 수 있다.	메모리 사용이 많다. 모든 인접 노드를 큐에 저장해야 하기 때문에 DFS보다 더 많은 메모리가 필요하다. 긴 경로를 탐색하는 데에는 시간이 더 오래 걸린다.

문제유형
DFS	BFS
경로에 특정 조건을 부여하여 확인하는 문제 * 경로의 중복된 값을 제거하는 문제 검색 대상이 큰 문제	미로 찾기 최단경로 찾기 검색 규모가 크지 않은 탐색 검색 시작점과 목표가 가까운 탐색