알고리즘/활용 방법
DFS/BFS 활용 문제
G_Gi
2021. 1. 6. 17:10
SMALL
DFS 와 BFS 언제 사용?
- 보통 문제들을 보면 DFS와 BFS를 둘 다 사용하여 풀 수 있다. (모든 정점들을 탐색하는 알고리즘)
- BFS는 최단경로 문제, 가중치 없는 그래프 문제에 적합하다. (미로 같은 문제)
- DFS는 경로의 특징을 저장해야 하는 문제에 적합하다. 가중치 관리가 용이하고 탐색에 대한 제약 조건이 있는 문제
- 위상정렬에도 DFS를 사용한다고 한다. DFS출력값의 역순은 위상정렬의 결과와 같다.
참고
LIST