BFS/DFS 탐색 개념 정리

코딩테스트를 풀다보면 꼭 만나면 BFS와 DFS를 정리해보면서 기본을 다져보려 해요!

 

자료 참고 웹사이트 출처:

https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/

https://www.tutorialspoint.com/difference-between-bfs-and-dfs#:~:text=BFS%2C%20stands%20for%20Breadth%20First,to%20find%20the%20shortest%20path.

BFS (Breadth First Search, 넓이 우선 탐색) - Level order

• 최단거리 검색을 위해 Queue 사용 -> First in Frist Out (FIFO) 개념 사용
• 전체 노드를 같은 레벨에서 돌며 진행되는 traversal approac (순회적 접근) 사용
• 타겟이 가까울 때 유용함 
• 전체를 탐색하기 때문에 DFS보다 느림
• Backtracking (역추적 불가)

출처: tutorialspoint (BFS구조)

 

DFS (Depth First Search, 깊이 우선 탐색) - Preorder, Inorder, Postorder

• 단거리 탐색을 위해 Stack 구조 사용 -> Last in Frist Out (LIFO) 개념 사용
• DFS 역시 traversal approach 이지만 root node에서 시작해서 최대한 멀리 갔다가 돌아오는 형식
• 타겟이 멀리 있을 때 유용함
• 재귀적 알고리즘 사용으로 backtracking 가능

출처: tutorialspoint (DFS구조)

---

DFS 관련 예제를 알고 싶으시다면 아래 게시물을 참고하시길!

https://psygo22.tistory.com/25

Leet code #94 Binary Tree Inorder Traverse (DFS, BFS)