[Section2][자료구조/알고리즘] 자료구조

제뉴어리맨 2022. 7. 28. 00:13

DFS (Depth-First Search) 란?

깊이를 먼저 탐색하는 탐색 방법이다.

한 깊이를 끝까지 탐색한 뒤 더 이상 탐색할 하위가 없을 경우 다른 깊이를 탐색한다.

DFS의 종류로는 아래와 같다

- 구현 가능 방법 종류

Stack 이용.

재귀 이용.

같은 레벨의 노드들을 먼저 탐색 하는 방법이다.

쉽게 말하자면,

root의 기준에서 자식 레벨의 모든 노드를 다 방문하고,

그 다음은 자식의 자식 노드들을 다 방문하기를 반복한다.

- 구현 가능 방법 종류

Queue 이용