DFS/BFS 활용 문제

DFS 와 BFS 언제 사용?

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

 

 

참고

- devuna.tistory.com/32

- ssssum.tistory.com/3