1️⃣ 개념
| 구분 | 완전탐색(Brute Force) | BFS / DFS |
|---|---|---|
| 정의 | 가능한 모든 경우의 수를 다 시도해 보는 탐색 방법 | 그래프나 트리 구조에서 경로를 따라 탐색하는 방법 |
| 접근 방식 | 무차별 대입 / 모든 후보를 시도 | 상태를 연결 관계로 이동하며 탐색 (재귀/스택/큐 활용) |
| 대상 | 주로 순열, 조합, 문자열, 숫자 등 모든 후보가 유한한 문제 | 그래프, 트래, 맵 등 노드와 간선이 존재하는 문제 |
2️⃣ 특징
| 구분 | 완전탐색 | DFS | BFS |
|---|---|---|---|
| 구현 | 반복문, 재귀로 단순 구현 가능 | 재귀 또는 스택 | 큐 |
| 메모리 사용 | 상대적으로 적음 (모든 경우를 순차적으로 처리 | 최대 경로 길이만큼 스택 필요 | 최대 레벨 노드 수만큼 큐 필요 |
| 시간 복잡도 | 후보 수에 따라 매우 커질 수 있음 (O(N!) 등) | 그래프 전체 노드를 한 번씩 방문 (O(V+E)) | 그래프 전체 노드를 한 번씩 방문 (O(V+E)) |
| 최적해 보장 | 모든 경우를 다 탐색하므로 최적해 보장 가능 | 경로/조건에 따라 최적해를 보장하지 않을 수 있음 | 최단경로 보장 (단, 가중치 없는 그래프) |
3️⃣ 활용 사례
| 구분 | 완전탐색 | DFS | BFS |
|---|---|---|---|
| 예시 문제 | - 순열/조합 문제 - 모든 부분집합 탐색 - 문자열 가능한 모든 조합 | - 미로 찾기 - 그래프 연결 요소 탐색 - 백트래킹 문제 | - 최단 경로 문제(unweighted) - 최소 이동 횟수 문제 - 레벨별 탐색 |
4️⃣ 관계
- DFS/BFS는 완전탐색의 한 종류로 볼 수 있음
- 완전탐색은 "모든 경우를 다 시도"하는 전략을 의미하고, DFS/BFS는 구조화된 방식으로 탐색하여 시간/공간을 효율적으로 관리함
- 따라서, 단순한 경우의 수가 적으면 완전탐색 → 경우 많으면 DFS/BFS(혹은 백트래킹/가지치기)로 확장
5️⃣ 추가 팁
- 완전탐색 → 단순 구현, 코드 직관적
- DFS → 재귀, 백트래킹, 깊이 우선 탐색
- BFS → 큐, 최단 경로, 레벨별 탐색
- 문제 크기(N)에 따라 완전탐색은 금방 시간초과 → DFS/BFS로 최적화 가능
