BFS / DFS 탐색 시각화
너비우선탐색(BFS)과 깊이우선탐색(DFS)을 그리드에서 비교합니다
탐색★☆☆
속도
1 / 1방문 노드: 0대기열 크기: 0
그리드 크기15 x 20
시작점 목표점 벽 방문 탐색 대기 경로
BFS는 큐(FIFO)를 사용하여 시작점에서 가까운 노드부터 레벨별로 탐색합니다.
각 단계에서 어떤 노드가 탐색되는지 관찰하세요.
BFS와 DFS란?
BFS(너비우선탐색)와 DFS(깊이우선탐색)는 그래프/트리 탐색의 가장 기본적인 두 알고리즘입니다. BFS는 시작점에서 가까운 노드부터 탐색하고, DFS는 한 방향으로 끝까지 탐색한 후 돌아옵니다.
사용 방법
- 1그리드를 클릭/드래그하여 벽을 그리거나 지우세요
- 2시작점(녹색)과 목표점(빨간색)을 설정하세요
- 3BFS, DFS, 또는 동시 비교 모드를 선택하세요
- 4재생 버튼으로 탐색 과정을 단계별로 관찰하세요
- 5랜덤 미로 버튼으로 다양한 시나리오를 실험하세요
동작 원리
- 1BFS — 시작 노드를 큐에 삽입하고, 큐에서 꺼내 인접 노드를 모두 큐에 추가(방문 표시)합니다. 큐가 빌 때까지 반복하여 레벨(깊이) 순서로 탐색합니다.
- 2DFS — 시작 노드를 스택에 삽입하고, 스택에서 꺼내 인접 노드 중 미방문 노드를 스택에 추가합니다. 스택이 빌 때까지 반복(또는 재귀 호출)하여 한 경로를 끝까지 탐색 후 백트래킹합니다.
- 3BFS의 큐는 FIFO라서 가까운 노드가 먼저 처리되고, DFS의 스택은 LIFO라서 가장 최근에 발견된 노드가 먼저 처리됩니다.
- 4두 알고리즘 모두 O(V+E) 시간 복잡도를 가지며, 그리드에서는 O(행×열)입니다.
실무 활용
- •BFS — 소셜 네트워크의 'n촌 관계' 탐색(LinkedIn 1촌/2촌)과 네비게이션의 최단 경로(비가중 그래프)에 사용됩니다.
- •BFS — 웹 크롤러가 레벨별로 링크를 수집할 때 사용하며, 시작 페이지에서 거리 순으로 탐색합니다.
- •DFS — 미로 찾기와 퍼즐 풀이, 컴파일러의 구문 트리 순회, Git의 커밋 히스토리 탐색에 활용됩니다.
- •DFS — 위상 정렬(빌드 의존성 순서 결정)과 강한 연결 요소(SCC) 탐색에 필수적입니다.
비슷한 알고리즘
- •BFS vs DFS — BFS는 최단 경로를 보장(비가중)하지만 메모리 O(V)가 필요합니다. DFS는 메모리 효율적이나 최단 경로를 보장하지 않습니다.
- •A* — BFS의 확장으로 휴리스틱을 사용해 목표 방향으로 효율적으로 탐색하여 훨씬 빠르게 최단 경로를 찾습니다.
- •다익스트라 — BFS의 가중치 버전으로 우선순위 큐를 사용하여 가중치 있는 그래프의 최단 경로를 찾습니다.
학습 팁
- •BFS는 최단 경로를 보장합니다 (가중치 없는 그래프에서)
- •DFS는 메모리를 적게 사용하지만 최단 경로를 보장하지 않습니다
- •좁은 통로가 있는 미로에서 두 알고리즘의 탐색 패턴 차이를 관찰하세요
- •동시 비교 모드에서 방문 노드 수와 경로 길이를 비교해보세요
자주 묻는 질문
Q. BFS가 항상 DFS보다 나은가요?
A. 아닙니다. BFS는 최단 경로가 필요할 때, DFS는 모든 경로 탐색이나 위상 정렬 등에 적합합니다. 메모리도 DFS가 유리합니다.
Q. 시간 복잡도는 어떻게 되나요?
A. 둘 다 O(V + E) — V는 노드 수, E는 간선 수입니다. 그리드에서는 O(행 × 열)입니다.
Q. A* 알고리즘과의 관계는?
A. A*는 BFS를 확장한 것으로, 휴리스틱(목표까지의 예상 거리)을 사용해 탐색 방향을 결정합니다. BFS보다 훨씬 효율적으로 최단 경로를 찾습니다.