깊이 우선 탐색 (DFS: Depth-First Search)
: 현재 정점에서 갈 수 있는 점들을 끝까지 방문하면서 탐색하는 방법
깊이 우선 탐색은 가장 마지막에 만났던 갈림길(간선)이 있는 정점으로 돌아가 다시 깊이 탐색을 해야하기 때문에
선입후출(First In Last Out) 방식인 스택(Stack)을 이용하여 구현할 수 있습니다.
참고로, 경로 탐색의 순서는 무조건 딱 한 가지 경로로만 정해져 있지는 않습니다.
시작노드에 부속되어 있는 자식노드들 중에 어떤 것을 먼저 탐색할지를 정하는 과정에서
동일한 그래프라도 하더라도 다른 경로가 나올 수도 있습니다.
깊이 우선 탐색 방법을 지키면서 탐색을 진행하셨다면, 이 글에서 보여드린 경로와 다른 경로가 나오더라도
그 경로는 옳은 경로가 될 것입니다.
그러면 스택(Stack)을 이용하여 위의 그림과 동일한 그래프를 다른 경로로 탐색해보겠습니다.
이해를 돕기 위해 직접 그림으로 그려보았습니다.
방법은 이와 같습니다.
1. 루트 노드(시작점)을 스택에 넣는다.
2. 루트 노드(시작점)을 스택에서 잠시 빼둔다.
3. 자식 노드를 모두 스택에 넣는다.
4. 3번 과정이 끝나면 루트 노드(시작점)는 방문이 완료된다. 따라서 루트 노드(시작점)을 방문 처리한다.
*여기서는 방문처리를 Print로 표현했습니다.
질문사항은 댓글 남겨주시면 감사드리겠습니다 :)