DFS와 BFS 선택 기준

💡 DFS와 BFS 선택의 기준

나는 대체로 DFS를 자주 사용하는 편이다.
상대적으로 DFS를 먼저 배우고 자주 사용해서 그런가..

그래서 문제마다 DFS, BFS 중 어떤 것을 사용해야 할지 고민한 경험이 많다.
코딩 테스트 문제에서 주로 이렇게 3가지 경우로 나뉘는거 같다.

1. DFS or BFS 어떤것이든 사용해도 무관한 경우
2. DFS를 사용하는것이 압도적으로 편한경우
3. BFS를 사용하는것이 압도적으로 편한경우

📌 DFS를 사용하자!

1. 연결된 그래프를 완전 탐색하는 경우
2. 모든 경우를 하나하나 다 탐색해야 하는 경우
3. 깊이 우선탐색이라는 개념을 가진 순열, 조합 구현에 활용

📌 BFS를 사용하자!

1. DFS와 마찬가지로 연결된 그래프를 완전 탐색하는 경우
2. depth(깊이)를 계산해야 하는 문제에 활용
   ex) 최단 경로의 길이 = depth(깊이)
3. 가중치가 같은 그래프에서 최단거리를 찾는데 활용

---

Reference

BLUE_ERASER님) PS를 하며 느끼는 DFS와 BFS 선택의 기준