BFS(Breadth-First Search)
- 너비 우선 탐색
- 노드 레벨 순서에 따라 순회:
부모 노드 기준으로 바로 자신의 자식 노드 레벨을 모두 살피고 해당 자식 노드들의 바로 아래의 자식 노드 레벨을 탐색한다. - 자료구조 Queue와 중복 방문 방지를 위한 배열이나 객체를 활용할 수 있다.
- 최단 경로를 알아내야 하는 경우 또는 찾아야 하는 노드가 인접한 경우 사용한다.
DFS(Depth-First Search)
- 깊이 우선 탐색
- 연결되어 있는 노드를 우선하여 순회:
부모 노드 기준으로 자신의 자식 노드 중 하나를 탐색하고 해당 자식 노드의 자식 노드를 탐색하는 순서로 탐색한다. - 자료구조 Stack 및 재귀를 활용할 수 있다.
- 경로를 완벽하게 탐색해야 할 때 사용한다.
BFS vs DFS
Log