Page 406 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

너비 우선 탐색
1
너비 우선 탐색(breadth-first Search)은 낮은 레벨에 A
서 시작해 왼쪽에서 오른쪽 방향으로 검색하고 한 2 B 3 C
레벨에서의 검색이 끝나면 다음 레벨로 내려갑니다. 4 5 6 7
D E F G
그림 10-3은 너비 우선 탐색으로 노드를 스캔하는 8 9 10 11 12
H I J K L
과정을 나타낸 것입니다. 검색 순서는 다음과 같습
니다. [그림 10-3] 너비 우선 탐색

A  B  C  D  E  F  G  H  I  J  K  L

깊이 우선 탐색

깊이 우선 탐색(depth-first Search)은 리프까지 내려 A
가면서 검색하는 것을 우선순위로 하는 탐색 방법입
B C
니다. 리프에 도달해 더 이상 검색을 진행할 곳이 없
D E F G
는 경우에는 부모에게 돌아갑니다. 그런 다음 다시
자식 노드로 내려갑니다. 그림 10-4는 깊이 우선 탐 H I J K L
색을 진행하는 과정을 나타낸 것이고, 그림 10-5는
[그림 10-4] 깊이 우선 탐색
노드 A를 몇 번 지나갔는지를 나타낸 것입니다. 다
음과 같이 깊이 우선 탐색을 진행하면서 노드 A를 3
회 지나갔음을 알 수 있습니다.

① 출발하려고 하는 ② 되돌아오면서
1. A에서 B로 내려가며 A를 지나갑니다. 경우에 노드 A를 방 노드 A를 방문하
문하는 경우 는 경우
2. B에서 C로 지나가며 A를 지나갑니다. A
3. C에서 A로 되돌아오면서 A를 지나갑니다.
B C

③ 지나가면서 노드 A를
다른 노드의 경우도 마찬가지로 생각하면 됩니다. 방문하는 경우
두 자식 가운데 한쪽(또는 양쪽)이 없으면 노드를 지
[그림 10-5] 깊이 우선 탐색에서 가능한 방문 종류
나가는 횟수가 줄어들겠지만 노드를 지나가는 최댓

값은 3회입니다. 그런데 깊이 우선 탐색을 진행하면
서 ‘언제 노드를 방문할지’는 다음과 같이 세 종류로
구분합니다.

친구의 집도 지나치는 것과 직접 방문하는 것은 다릅니다. 이와
마찬가지로 깊이 우선 탐색도 지나가는 것과 방문하는 것을 구분해
서 생각합니다.

406 C 알고리즘