DFS & BFS

그래프

• 정점과 간선으로 이루어진 자료구조
• 정점 : 노드
• 간선 : 정점을 연결한 선
• 트리 : 그래프 중에서 방향성이 있는 비순환 그래프

그래프 vs 트리

DFS(깊이 우선 탐색)

• 최대한 깊이 내려간 뒤, 더이상 갈 곳이 없을 경우 옆으로 이동
• 즉, 한 노드와 연결된 노드를 끝까지 탐색 후 다음 인접 노드로 넘어가는 것

1. 모든 노드를 방문하고자 할 때 선택
2. DFS가 BFS보다 좀 더 간단하다
3. 검색속도는 BFS보다 느리다

BFS(넓이 우선 탐색)

• 최대한 넓게 이동하고, 끝까지 간 후 아래로 이동
• 루트 노드에서 인접한 노드를 먼저 탐색하고, 멀리 떨어진 노드를 나중에 탐색

1. 두 노드 사이의 최단 경로를 찾을 때 사용
2. DFS의 경우 모든 경우를 봐야하고 특정 노드를 찾을 때 처음 탐색한 경로가 찾는 노드가 있으면 다행이지만 아닐 경우 시간을 소비하게 됨

DFS vs BFS

• DFS : 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색, 스택 또는 재귀함수로 구현
• BFS : 현재 정점에서 가까운 점들부터 탐색, 큐로 구현

활용

1. 그래프의 모든 정점을 방문하는 것이 중요한 문제
   • DFS, BFS의 시간복잡도는 같기 때문에 어느것을 사용하여도 상관없다
2. 경로의 특징을 저장해야하는 문제
   • a에서 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다는 문제 등, 각각의 경로 특징을 저장해야할 때
   • DFS 사용 (BFS는 경로의 특징을 가지지 못한다)
3. 최단거리를 구해야 하는 문제
   • BFS 사용
   • DFS의 경우 처음 탐색하는 경로에 원하는 노드가 없을 수도 있기 때문
4. 기타
   • 검색 대상의 그래프가 큰 경우 DFS 고려
   • 규모가 크지 않고, 검색 시작 지점과 찾는 대상의 거리가 멀지 않다면 BFS