DFS(Depth-First Search) / BFS(Breadth-First Search)

그래프나 트리 관련 문제 나오면, BFS/DFS로 풀어야할 가능성 높음!!

• DFS는 경로 찾기,탐색을 끝까지 진행하는 문제

  • 모든 경우의 수 찾기
  • 연결된 컴포넌트 탐색 등

• BFS는 보통 최단거리 문제, 레벨별 탐색 문제

  • 최단 경로
  • 레벨별 출력 등

📘 DFS

먼저 깊게 파고들어간 후, 더 이상 갈 곳이 없으면 다시 돌아오는 방식으로 탐색

✨ 특징

• 한 경로를 끝까지 탐색
• 현재 노드에서 자식노드로 계속 깊이 들어가다가 더이상 갈 곳이 없으면 되돌아와서 다른 경로 탐색
• 트리 or 그래프에서 한 뱡향으로 깊이 파고들면서 탐색

📘 BFS

넓게 탐색하는 방식, 한번에 모든 노드 탐색 -> 자식노드 탐색

현재 노드와 같은 깊이의 노드들 먼저 탐색 후, 아래로 내려가서 탐색

✨ 특징

• 현재 경로에서 한 단계씩 확장하면서 탐색
• 모든 노드 한번에 탐색 후, 자식 노드 탐색 방식
• 너비 우선(같은 레벨 노드 먼저)