728x90
반응형
Graph와 비선형 탐색 📚
Graph, 너비우선탐색(BFS)/ 깊이우선탐색 (DFS)
📌 Graph (그래프)
- 정의: 노드(Vertex, 정점)와 간선(Edge)으로 이루어진 자료구조
- 종류
방향 그래프 (Directed Graph): 간선에 방향 존재 (A → B)무방향 그래프 (Undirected Graph): 간선에 방향 없음 (A ↔ B)가중치 그래프 (Weighted Graph): 간선에 비용/가중치 존재
📌 그래프 탐색 방법
1️⃣ 깊이 우선 탐색 (DFS: Depth First Search)
- 한 방향으로 최대한 깊이 탐색 후, 더 이상 갈 곳이 없으면 백트래킹(되돌아감)
- 보통 재귀 호출 또는 스택으로 구현
- 적합한 상황: 모든 경우 탐색, 경로 찾기, 조합/순열 문제
2️⃣ 너비 우선 탐색 (BFS: Breadth First Search)
- 루트에서 가까운 노드부터 레벨 단위로 탐색
- 보통 큐(Queue) 로 구현
- 적합한 상황: 최단 경로 문제 (예: 미로 탐색, 최단 거리 찾기)
⭐️ 그래프 예시와 탐색 순서
A
/ \
B C
| |
D E- DFS (깊이 우선 탐색)
- 시작: A
- 순서:
A → B → D → C → E - BFS (너비 우선 탐색)
- 시작: A
- 순서:
A → B → C → D → E
📌 DFS vs BFS 비교 정리
| 구분 | DFS (깊이 우선 탐색) | BFS (너비 우선 탐색) |
| 탐색 방식 | 한 경로를 끝까지 파고든 후 되돌아옴 (백트래킹) | 시작점에서 가까운 노드부터 차례대로 탐색 (레벨 단위) |
| 자료구조 | 스택(Stack) 또는 재귀(Recursion) | 큐(Queue) |
| 탐색 순서 예시 (그래프: A-B-D, A-C-E) | A → B → D → C → E | A → B → C → D → E |
| 적합한 상황 | - 모든 경우 탐색 (완전탐색, 백트래킹) - 경로 유무 확인 |
- 최단 거리 탐색 - 레벨 단위 탐색 |
| 시간 복잡도 | O(V + E) (V=정점, E=간선) | O(V + E) (V=정점, E=간선) |
| 특징 | - 깊게 들어감 - 재귀 활용 쉬움 - 경우의 수 탐색 적합 |
- 넓게 탐색 - 최단 경로 보장 - 레벨 순회 용이 |
✅ 정리
- DFS: 깊이 우선, 모든 경우 탐색 / 백트래킹 활용
- BFS: 너비 우선, 최단 거리 보장 / 큐 활용
➡️ 즉, "최단 거리" 문제면 BFS,
➡️ "모든 경우 확인(조합, 경로 유무)" 문제면 DFS 가 적합
728x90
반응형