BFS와 DFS 비교표

BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)의 특징을 비교

특징	BFS(너비 우선 탐색)	DFS(깊이 우선 탐색)
탐색 방식	너비 우선 탐색	깊이 우선 탐색
구조	큐(Queue) 사용	스택(Stack) 또는 재귀 사용
최단 경로	가중치가 없는 경우 최단 경로 보장	최단 경로 보장하지 않음
메모리 사용	O(V) (정점 수)	O(V) (정점 수)
시간 복잡도	O(V + E) (정점과 간선 수)	O(V + E) (정점과 간선 수)
적용 분야	최단 경로, 네트워크 탐색, 퍼즐 문제	미로 찾기, 위상 정렬, 연결 요소 찾기
방문 순서	인접한 정점부터 탐색	한 방향으로 깊게 탐색
중복 경로	동일한 정점 여러 번 방문 가능	동일한 정점 여러 번 방문 가능
전략	레벨 단위로 탐색	경로 단위로 탐색
실제 적용 예시	소셜 네트워크 분석, 웹 크롤러, GPS 내비게이션	게임 AI(경로 찾기), 컴파일러(위상 정렬), 퍼즐 솔버