[C++] 트리 #2 DFS

목차

※ 트리 #1 Tree

 

1. 깊이 우선 탐색이란?

2. DFS 구현

---

1. 깊이 우선 탐색이란? (DFS : Depth First Search)

- 그래프에서 깊은 부분을 우선적으로 탐색

- 리프 노드에 도달 할 때 까지 목표 노드를 탐색, 발견 되지 않으면 현재 탐색 중인 노드의 부모 노드에서 탐색 되지 않은 자식 노드를 탐색한다. (백 트래킹 : backtracking) 

ㄴ 노드 방문 시 방문 여부를 검사해야 무한 루프를 방지할 수 있다 (탐색 된 노드 재탐색 방지)

 

- 장점 : 현재 경로만 저장하며 탐색하므로 메모리를 적게 사용한다 (단순 탐색에 비해), 목표 노드가 깊이 있다면 빠르게 구할 수 있다.

 

- 단점 : 탐색된 결과가 최단 경로가 아닐 수 있다. (목표 경로가 여럿일 경우), 목표 노드가 없는 경로를 필요 없이 계속 탐색 할 수도 있다. (탐색 깊이 제한을 주면 해결 됨)

 

DFS 애니메이션 (출처 : 위키백과)

 

 

2. DFS 구현

 

가. 재귀 구현 (※ 입력 기준 : DFS 애니메이션)

DFS 탐색 경로 출력

 

나. 스택 구현

DFS 탐색 경로 출력

스택 진행 과정 애니메이션

 

※ 참조

위키 백과 깊이 우선 탐색 :

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