DFS와 BFS에 대해 설명해주세요.
DFS(깊이 우선 탐색)
- 한 브랜치를 가능한 깊게 전부 확인한 후 다음 브랜치를 탐색
- 탐색 순서에 따라 구분
Pre-Order
- 루트 노드에서 시작해 서브 브랜치들을 순회
- 트리를 복사하기 위해 전체 구조를 순회할 때 유리
In-Order
- 한쪽에서 부터 서브 브랜치를 순회하기 시작
- 이후 루트를 거쳐 다음 서브 브랜치로 이동
Post-Order
- 모든 서브 브랜치를 먼저 순회한 다음 루트로 이동
- 브랜치 내부 요소를 순차적으로 제거할 때 사용하기에 유리
BFS(너비 우선 탐색)
-
'node'들의 레벨을 구분하고, 각각의 레벨들을 먼저 탐색
-
여기서 레벨은 루트 노드를 레벨 0으로 할 때를 기준으로 함
루트 노드에서 연결된 서브 노드 = 레벨 1
해당 서브 노드에서 연결된 또 다른 서브 노드 = 레벨 2 -
가장 가까운 노드부터 탐색할 때 유리
