DFS와 BFS

탐색 알고리즘에 DFS와 BFS가 있습니다.

DFS(Depth First Search)

DFS는 깊이우선탐색트리로 불리며, 먼저 들어온 노드를 중심으로 계속 탐색해 나가는 방식입니다.

위의 트리를 탐색하는 순서는 A->B->D->E->C->F->G 순으로 탐색을 합니다.

DFS 구현은 스택을 사용하여 가능하기에, 주로 재귀함수를 사용합니다. 장점은 마지막 방문한 노드의 데이터만 저장하면 되기에 공간이 절약됩니다. 단점은 노드의 깊이가 깊으면 성능이 떨어지고 최단경로가 된다는 보장이 없습니다.

BFS(Breath First Search)

BFS는 넓이우선탐색트리로 불리며, 먼저 들어온 노드가 인접한 노드를 순서대로 탐색해 나가는 방식입니다.

위의 트리를 탐색하는 순서는 A->B->C->D->E->F->G순으로 탐색을 합니다.

BFS 구현은 큐를 사용하여 가능합니다. 장점은 목표노드까지의 최단경로를 보장합니다. 단점은 모든 노드들의 저장할 공간을 요구합니다.