[알고리즘]깊이우선탐색(DFS)

깊이 우선 탐색(DFS)

그래프 탐색이란?

• 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것.

깊이 우선 탐색이란?

• Root 노드(혹은 다른 임의의 노드)에서 시작하여, 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽히 탐색하는 방법.
• 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
• 단순 검색 속도 자체는 BFS보다 느리다.

깊이 우선 탐색의 특징

• 자기 자신을 호출하는 순환 알고리즘 의 형태를 가진다.
• 전위 순회(Pre-order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
• 이 알고리즘을 구현할 때의 가장 큰 차이점은, 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다.
  • 이를 검사하지 않을 경우 무한 루프에 빠질 수 있다.

1. a 노드(시작 노드)를 방문한다.
   • 방문한 노드는 방문했다고 표시를 한다.
2. a와 인접한 노드들을 차례로 순회한다.
   • a와 인접한 노드가 없다면 종료한다.
3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 이전에, b와 인접한 노드들을 전부 방문해야만 한다.
   • b를 정점으로 DFS를 다시 시작하여, b의 이웃 노드들을 방문한다.
4. b의 분기를 전부 완벽하게 탐색했다면, 다시 a에 인접한 정점들 중에서 아직 방문이 되지 않은 정점을 찾는다.
   • 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드들을 방문할 수 있다는 것.
   • 모두 방문을 했다면 종료.
   • 아직 방문을 하지 않은 정점이 있다면, 그 정점을 시작 정점으로 삼고 DFS를 시작.

깊이 우선 탐색(DFS)의 구현

• 구현 방법 2가지
  1. 순환 호출을 이용
  2. 명시적인 스택을 사용
     • 명시적인 스택을 사용하여 방문한 정점들을 스택에 저장하였다가 다시 꺼내어 작업한다.

아래 블로그를 참고하여 작성하였습니다.
https://github.com/WeareSoft/tech-interview