[DFS]
깊이 우선 탐색(DFS, Depth First Search)
: 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
: 하나의 경로를 끝까지 탐색한 후 다음 경로로 넘어가 탬색을 진행
: BFS보다 탐색 시간은 오래걸리지만 모든 노드를 완전히 탐색 가능함 >> 모든 노드를 방문해야 하는 경우 사용
: BFS보다 좀 더 간단히 사용 가능함
>> 스택 또는 재귀함수로 구현함
[BFS]
너비 우선 탐색(BFS, Breathed First Search)
: 그래프에서 가까운 노드를 우선적으로 탐색하는 알고리즘
: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
: 너비를 우선적으로 탐색하는 방법으로 정점 사이의 최단 경로를 찾을 때 사용
>> 최악의 경우 모든 정점을 다 살펴야 함
>> 큐를 이용해서 구현함
[문제 유형]
1. 그래프의 모든 정점을 방문하는 것이 주요한 문제일 경우
: DFS, BFS 두 방법중 어느것을 사용해도 무방함
2. 경로의 특징을 저장해야 하는 경우
: DFS를 사용해야 함 (BFS는 경로의 특징을 가지지 못하기 때문)
3. 최단 거리를 구해야 하는 경우
: BFS가 유리 (DFS의 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있으나, BFS는 가까운 노드부터 탐색을 진행하기 때문)
'공부 자료 > 자료구조|알고리즘' 카테고리의 다른 글
| [자료구조/알고리즘] 완전 탐색 / 이진 탐색 알고리즘 (0) | 2022.10.01 |
|---|---|
| [자료구조/알고리즘] 탐욕 알고리즘 Greedy (0) | 2022.10.01 |
| [자료구조/알고리즘] 시간복잡도 (0) | 2022.10.01 |
| [알고리즘/자료구조] 자료구조 (1) | 2022.10.01 |
| [자료구조/알고리즘] 재귀 (0) | 2022.09.30 |
