DFS, BFS 모두 그래프를 탐색하는 방법이다. 여기서 그래프는 노드와 그것을 연결하는 선으로 이루어진 구조를 말한다.
🐱👤DFS
1) 루트노드에서 시작하여 다음 분기로 넘어가기 전, 해당 분기를 완벽하게 탐색하는 방법
2) stack 혹은 재귀함수(recursion)으로 구현
+) DFS를 사용하는 경우, DFS 문제
1. 보통 모든 노드를 방문(완전 탐색)하고자 하는 경우에 사용한다(BFS가 효과적인 경우가 있긴 하다.).
2. 경로의 특징을 저장해야 하는 경우에 사용한다.
3. 검색 대상의 그래프가 큰 경우에 사용하는 편이다.
🐱💻BFS
1) 루트노드에서 시작하여 인접 노드를 먼저 탐색하는 방법
2) 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문한다.
3) 큐(queue)를 사용하여 구현한다.
+) BFS를 사용하는 경우
1. 가까운 노드부터 탐색하고자 할 때 사용한다.
2. 검색 대상의 규모가 크지 않고, 최단거리를 구하는 문제에서 사용하는 편이다.
@sonyrainy