DFS의 장점
현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용
찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있음
DFS의 단점
해가 없는 경로를 탐색할 경우에도 단계가 끝날 때까지 탐색
효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용하기도 함.
DFS를 통해서 얻어진 해가 최단경로라는 보장이 없음(DFS는 해에 도착하면 탐색을 종료하기 때문에)
BFS의 장점
최단경로를 찾을 수 있음
BFS의 단점
경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간 필요
'📚전공 > 알고리즘' 카테고리의 다른 글
| [알고리즘] [그래프 탐색] DFS(깊이 우선 탐색) (0) | 2023.02.20 |
|---|---|
| [알고리즘] 다이나믹 프로그래밍 (DP) (0) | 2023.01.04 |
| [알고리즘] 그리디 알고리즘 (Greedy, 탐욕법) (0) | 2021.06.30 |
| [알고리즘] 병합 정렬 (Merge Sort) (0) | 2021.05.23 |
| [알고리즘] Selection Sort(선택 정렬) (0) | 2021.05.23 |
