언제 DFS, BFS를 사용하는지 궁금해 찾아보다가 이 궁금증을 잘 정리해준 사이트를 발견해 관련 부분을 발췌하였다.

평소에 DFS, BFS 둘 다 써도 되는 문제들만 풀어서 언제 DFS, BFS를 써야 하는지 궁금했는데 덕분에 잘 정리되었다!

DFS, BFS의 적합한 문제 유형

📌 DFS, BFS 모두 적합한 유형

단순히 모든 정점을 방문하는 것이 중요한 문제인 경우 어떤 것을 택해도 된다.

📌 DFS가 적합한 유형

검색 대상 그래프가 큰 경우(정점과 간선의 개수가 많음)
경로의 특징을 저장해둬야 하는 문제
ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다는 문제
BFS는 경로의 특징을 가지지 못함

📌 BFS가 적합한 유형

미로찾기 등 최단거리를 구해야 할 경우
DFS는 처음으로 발견되는 해답이 최단거리 라는 것 보장 X
반면 BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 경로 탐색 시 첫번째로 찾아지는 해답이 곧 최단거리이다.

(ref) DFS, BFS의 설명, 차이점