깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

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

대표적으로 백트래킹에 사용한다. 일반적으로 재귀 호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다.

자동 미로 생성에 많이 사용 되는 알고리즘!

장점

• 현 경로상의 노드만 기억하면 돼서 저장공간의 수요가 비교적 적다.
• 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

• 해가 없는 경로에 깊이 빠질 수 있다. ( 임의 깊이까지만 탐색하도록 만들기! )
• 얻어진 해가 최단 경로가 아닐 수도 있다.
  왜냐? DFS는 일단 해를 찾으면 탐색이 끝나기 때문이다.

동작 방식

출처 :  https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 

우선 그래프에서의 깊이(depth)를 결정할 필요가 있다.

루트 노드의 깊이는 0으로 하고,

임의의 노드의 깊이는 이 부모 중 가장 깊이가 작은 것의 깊이에 1을 더한 값!!

따라서 그래프에서의 깊이 우선 탐색은 OPEN에 있는 노드 중 가장 깊은 것을 택하여 확장시키게 된다. 후계 노드가 생성되어 이 중에 이미 OPEN이나 CLOSED에 있는 것이 있다면, 깊이를 재조정하여야 한다.

여기서 알 수 있는 것은 일반적인 그래프를 탐색하는 경우라도, 탐색 과정에 의하여 얻어지는 노드들과 포인터들은 역시 탐색 트리를 형성한다는 것이다. 즉, 포인터들은 오직 하나의 부모를 가리키게 된다.

---

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

깊이 우선 탐색(DFS)과는 다르게 가까운 노드부터 탐색하는 알고리즘이다.

노드 수가 적고 깊이가 얕은 해가 존재할 때 유리하다!

 

장점

• 답이 되는 경로가 여러 개인 경우 최단 경로를 찾아내기 쉬움
• 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다.

단점

• 큐를 이용해 노드를 저장하기 때문에 노드의 수가 많을수록 필요한 저장공간의 크기 비약적으로 커짐.
• 불필요하게 탐색해야 하는 노드가 많다.

동작 방식

출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

루트 노드에서 시작하여 루트 노드에 인접하는 방문한 적 없는(큐에도 없는) 노드를 큐에 넣는다.

큐에 들어가는 순서대로 노드를 탐색하며 큐를 방문할 때 해당 큐와 인접한 노드를 또 큐에 넣는다!

위에 애니메이션에서 회색은 큐의 상태를 보여주며 검은색은 실제로 탐색하는 노드의 순서다.