깊이 우선 탐색(DFS, Depth-First-Search)

개념

루트 노드 (혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 가장 가까운 분기점으로 돌아와서 이곳부터 다시 다른 방향으로 다시 탐색을 진행하는 방법이다.
• 깊게(deep) 탐색하는 것
• 사용하는 경우 : 모든 노드를 방문하고자 할 때
• DFS가 BFS보다 좀 더 간단하다.
• 단순 검색 속도 자체는 BFS보다 느리다

특징

• 자기 자신을 호출하는 재귀형식의 순환 알고리즘
• 전위순회를 포함한 다른형태의 트리 순회는 모두 DFS의 한 종류
• 어떤 노드를 방문했었는지 여부를 반드시 검사 (검사 안하면 무한루프)

깊이 우선 탐색 과정

깊이 우선 탐색의 구현

구현 방법 2가지