깊이 우선 탐색 (DFS)과 너비 우선 탐색 (BFS)

깊이 우선 탐색 (Depth First Search) 깊이 우선 탐색은 특정 노드에서 시작해, 최대한 깊숙히 탐색한 후에 다른 분기의 노드를 탐색하는 방식을 말합니다. 아래의 그림을 보면 조금 더 이해하기 쉬우실 것입니다. 특정 노드에서 맨 아래의 자손 노드까지 탐색한 후에 목표를 찾지 못했다면 다시 부모 노드로 돌아와 다른 갈림길에서 탐색을 반복합니다. 이때, 부모 노드로 돌아오는 과정을 백트래킹이라고 합니다. 깊이 우선 탐색은 다음과 같은 특징을 가집니다. 모든 경로를 방문해야 할 경우에 적합합니다. 주로 스택을 사용하여 구현합니다. 장점으로는 탐색 경로의 노드들만 기억하면 되므로, 그래프 높이 만큼의 공간만 필요하다는 장점을 가집니다. 단점으로는 목표가 되는 데이터가 없는 경로를 탐색하는 경우가 있..