DFS (Depth First Search) : 깊이 우선 탐색

트리나 그래프에서 한 경로로 끝까지 깊숙이 탐색하고 다시 돌아와 다른 경로로 탐색하는 과정이다.

한 경로의 탐색이 끝나면 다시 이전 과정으로 돌아가 다른 경로로 탐색을 반복하므로 스택이나 재귀를 사용하여 구현하는 경우가 일반적이다.

현 경로상의 노드만을 기억하면 되므로 저장 공간의 수요가 비교적 적지만, 한 경로가 무한히 깊을 경우 오버플로우가 발생할 수 있다. 이를 방지하기 위해 깊이에 제한을 두고 구현한다.

깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 가장 최근의 부모 노드로 돌아가(Backtraking) 다른 경로를 선택해 진행한다.

또한 목표 노드에 도달하지 못할 가능성이 존재하며, 도달한다 해도 해당 경로가 최단 경로라는 보장이 없다.

모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.

깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.

검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

BFS (Breadth First Search) : 너비 우선 탐색

트리나 그래프에서 루트 노드부터 탐색을 시작해 인접한 모든 노드를 탐색해 나가는 방법이다.

탐색해야 될 노드들을 저장해 놓고 하나씩 탐색해 나가면서 지우는 방식으로 큐를 이용해 구현하는 경우가 일반적이다.

해가 존재한다면 무조건 찾을 수 있는 방법이지만
경로가 긴 경우 저장 공간의 수요가 매우 커지게 되며 해가 존재하지 않는 경우 모든 노드의 탐색을 마친 후에 실패로 끝나게 된다.

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 BFS를 선택한다.

정리

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.
DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.

DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있다.

• 그래프의 모든 정점을 방문하는 것이 주요한 문제
  단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없다.

• 경로의 특징을 저장해둬야 하는 문제
  예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못한다.)

• 최단거리 문제
  미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리하다.
  왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
  너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문.

이밖에도,
검색 대상 그래프가 정말 크다면 DFS를 고려
검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS 등..