깊이우선 탐색(DFS), 넓이우선 탐색(BFS)

 깊이우선 탐색(DFS, Depth-first Search)과 넓이우선 탐색(BFS, Breadth-first Search)은 그래프에서 사용되는 가장 대표적이며, 어쩌면 맹목적인 두 가지 탐색 기법입니다. (맹목적인이라는 말을 언급한 이유는 기본적으로, 원하는 결과를 도출하기 위한 방향이 없이 해당 노드에서 모든 경우에 대하여 탐색을 수행하기 때문입니다.)

 두 가지 방식에 대한 차이는 탐색하는 모든 경우를 깊이에 우선하여 탐색을 수행할 것이냐, 넓이에 우선하여 탐색을 수행할 것이냐 라는 것입니다.

 깊이에 우선한다는 것은 현재 노드에서 이동 가능한(연결된) 다음 레벨의 노드를 확인한 후, 곧바로 현재 노드 위치를 선택된 다음 레벨의 노드로 변경한다는 것입니다. 이때, 다음 레벨의 노드에서 원하는 결과를 찾지 못할 때 돌아올 수 있도록 현재 노드 위치를 스택(Stack)을 사용하여 기억해야 합니다. 그래서 보통 문제 해결에 있어 재귀함수의 형태로 사용하는 편입니다. 또한, 이전의 부모노드로 돌아오는 이 과정을 백트래킹(Back-Tracking)이라고 합니다.

 넓이에 우선한다는 것은 현재 노드에서 이동 가능한(연결된) 다음 레벨의 노드들을 확인한 후, 다음 레벨의 노드들을 모두 큐(Queue)에 담습니다. 이후, 큐에 담긴 노드 위치들을 하나씩 꺼내며 현재 노드 위치를 변경한다는 것입니다. 이에 따라 그래프의 레벨 순서대로 모든 노드들을 탐색하게 됩니다.

 이해를 돕기 위해, 코드로 간단히 표현하자면 아래와 같습니다.

  아래와 같은 그래프(트리)가 있으며, 탐색을 수행하기 위한 시작 노드를 A라고 합시다.

 다음 레벨에 대한 탐색 순서를 알파벳 순이라고 가정했을 때, 전체적인 그래프 탐색순서는 다음과 같습니다.

 Depth-first Search: A, B, D, H, I, E, C, F, G, J, K

 Depth-first Search(백트래킹 포함): A, B, D, H, (D), I, (D), (B), E, (B), (A), C, F, (C), G, J, (G), K

 Breadth-first Search: A, B, C, D, E, F, G, H, I, J, K

 위의 두 가지 탐색 기법은 서로 상반된 장단점이 있습니다.

 

 깊이우선 탐색의 경우

 장점으로는, 현 경로상의 노드들만 기억하면 되므로 그래프의 높이 만큼의 공간만을 요구합니다. 따라서 최대 저장공간의 수요가 비교적 적습니다. 또한, 목표노드가 깊은 단계에 있을 경우에 해를 빠르게 구할 수 있습니다.

 단점으로는, 해가 없는 경로에 깊이 빠질 가능성이 있다는 것입니다. 또한 얻어진 해가 최단 경로가 된다는 보장이 없습니다. (목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이 때 얻어진 해는 최적의 해가 아닐 수 있습니다.)

 넓이우선 탐색의 경우

 장점으로는, 출발노드에서 목표노드까지의 최단 길이 경로를 보장합니다. (물론 모든 간선의 가중치가 동일할 경우입니다.)

 단점으로는, 최악의 경우 모든 노드에 대한 정보를 위한 공간을 요구한다는 것입니다. 따라서 최대 저장공간을 크게 잡아야 합니다. 또한 목표노드가 깊은 단계에 있을 경우 오랜 시간이 소요됩니다.

 사실 위의 두 탐색방식 모두 최악의 경우 모든 노드들을 탐색하게 되므로 많은 시간이 소요될 수 있습니다. 그래서 각 기법에 따라, 그리고 문제의 요구사항에 따라 힙(Heap)을 이용해 다음 레벨에 대한 노드탐색 순서에 대하여 우선순위를 두곤합니다. 혹은 분기한정법(혹은 가지치기, Branch and Bound)을 통해 알고리즘의 효율을 높일 수 있습니다.

참고 : https://ko.wikipedia.org/wiki/깊이_우선_탐색, https://ko.wikipedia.org/wiki/너비_우선_탐색