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

깊이우선 탐색이란?

깊이 우선 탐색은 그래프 완전 탐색 중 하나다.

DFS는 그래프 시작노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색하는 알고리즘이다. 

 

❗️ DFS 알아보기

- 기능: 그래프 완전 탐색

- 특징: 재귀 함수 구현, 스택(FIFO) 자료구조 이용

- 시간 복잡도: O(V+E)

- 문제 유형: 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬

* 깊이 우선 탐색 실제 구현 시 재귀함수를 이용하므로 스택오플로를 유의해야한다.

 

👉  깊이 우선 탐색의 핵심 이론

DFS는 한번 방문 한 노드를 다시 방문하므로 안되므로 노드 방문 여부를 체크할 배열이 필요하며, 

그래프는 인접리스트를 표현한다. 그리고 DFS 탐색 방식은 후입선출 특성을 가지므로 스택을 이용해서 설명하겠다. 

 

 

 

❗️ 1. DFS 시작할 노드를 정한 후, 사용할 자료구조 초기화하기

     -> 인접리스트로 표현

스택에 시작 노드를 1로 삽입 할 때, 해당 위치의 방문 배열을 체크하면 T,F,F,F,F,F가 된다.

 

❗️ 2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노트 다시 스택에 삽입하기

이제 POP을 수행하여 노드를 꺼냅니다.

꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하여 방문 배열을 체크합니다.

방문 배열은 T,T,T,F,F,F가 됩니다. 

 

 

❗️ 3. 스택 자료구조에 값이 없을 때 까지 반복하기

앞선 과정을 스택 자료 구조에 값이 없을 때 까지 반복합니다.

이 때 이미 다녀간 노드는 방문 배열은 재삽입 하지 않는 것이 핵심입니다. 

   

👉 핵심 정리 1: 

스택에 노드를 삽입할 때, 방문 배열을 체크하고

스택에서 노드를 뺄 때, 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하며 살펴보자.

 

👉 핵심 정리 2:  

모든 노트를 탐색하여 탐색 종료 -> DFS 총 2 회 수행.

즉, 연결 요소 개수는 2개. 

 

=> 모든 노드를 탐색하는데 실행한 DFS의 실행 횟수가 곧 연결 요소 개수와 같다.