📖BFS & DFS

📎탐색 방법

BFS

현재 정점에 연결된 가까운 노드부터 탐색

DFS

현재 정점에서 갈 수 있는 정점들까지 들어가며 탐색

📎구현 방법

BFS

큐를 이용해서 구현

DFS

재귀, 스택으로 구현

📎알고리즘 문제 유형

1. 그래프의 모든 정점을 방문하는 문제 → BFS, DFS
2. 경로의 특징을 저장해두어야 하는 문제 → DFS
   • 특정 경로에 같은 숫자가 있으면 안되는 문제
   • 목적지에 도달할 수 있는지를 탐색하는 문제
   • 최단거리로 갈 수 있는 경로의 수를 찾는 문제 ( ∵ BFS는 경로의 특징을 가지지 못함)
3. 최단거리를 구하는 문제 → BFS
   • 미로 찾기 ( ∵ DFS는 처음으로 발견되는 해답이 최단거리가 아닐 수 있음)
4. 그래프의 크기가 큰 문제 → DFS

📎시간복잡도

둘 다 모든 노드를 탐색하므로 시간복잡도 동일

그래프 구현 방법	시간복잡도
인접 행렬	O(n²)
인접 리스트	O(n+e)

• 둘 다 모든 노드를 탐색하므로 시간복잡도는 동일하지만, 일반적으로 DFS가 재귀로 구현한다는 점에서 DFS가 조금 더 빠르게 동작
• 일반적으로 인접 리스트 방식이 더 효율적