목차
1. 깊이 우선 탐색이란? (DFS : Depth First Search)
- 그래프에서 깊은 부분을 우선적으로 탐색
- 리프 노드에 도달 할 때 까지 목표 노드를 탐색, 발견 되지 않으면 현재 탐색 중인 노드의 부모 노드에서 탐색 되지 않은 자식 노드를 탐색한다. (백 트래킹 : backtracking)
ㄴ 노드 방문 시 방문 여부를 검사해야 무한 루프를 방지할 수 있다 (탐색 된 노드 재탐색 방지)
- 장점 : 현재 경로만 저장하며 탐색하므로 메모리를 적게 사용한다 (단순 탐색에 비해), 목표 노드가 깊이 있다면 빠르게 구할 수 있다.
- 단점 : 탐색된 결과가 최단 경로가 아닐 수 있다. (목표 경로가 여럿일 경우), 목표 노드가 없는 경로를 필요 없이 계속 탐색 할 수도 있다. (탐색 깊이 제한을 주면 해결 됨)
2. 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
'C++ > 자료구조' 카테고리의 다른 글
[C++] 정렬 #3 병합 정렬 & 퀵 정렬 (Merge Sort & Quick Sort) (0) | 2023.07.03 |
---|---|
[C++] 정렬 #2 삽입 정렬 & 힙 정렬 (Insertion Sort & Heap Sort) (0) | 2023.06.30 |
[C++] 정렬 #1 버블 정렬 & 선택 정렬 (Bubble Sort & Selection Sort) (0) | 2023.06.29 |
[C++] 트리 #3 BFS (0) | 2023.06.28 |
[C++] 트리 #1 Tree (0) | 2023.06.24 |