슬기로운 개발자

DFS - 깊이 우선 탐색 말 그대로 노드에 연결된 최하층 노드까지 탐색하고 다시 분기점에서 가지 않은 노드가 있다면 이동하는 방식으로 진행되는 탐색이다. DFS에는 스택과 재귀를 이용한 구현으로 나뉘게 되고, 방식에 따라 탐색순서가 달라질 수 있다. 1. 스택을 이용하는 경우 스택은 특성상 한 방향으로 입출력이 된다. 위 그림의 예시로 출력되는 순서와 방식을 알아보자. 1. 먼저 root인 A노드에서 시작한다. 2. A 노드가 출력되면, 이하 자식 노드인 B, C, D가 들어간다. 3. 위에서 출력되니까 D 노드가 출력되고 자식 노드인 H가 입력된다. 4. 맨 위에 있는 H 노드가 출력되고, 자식 노드는 없으므로 그 뒤에 있는 C 노드가 출력된다. 5. C 노드의 자식노드인 G 노드가 들어간다. 6. ..