[탐색 알고리즘] DFS - 깊이 우선 탐색 (Depth First Search)

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

그래프 완전 탐색 기법 중 하나이다.

완전 탐색이란 그래프의 모든 노드를 탐색 하는것을 의미한다.

 

그래프의 시작 노드에서 출발, 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른쪽 분기로 이동하여 다시 탐색 수행한다.

 

기능	특징(구현 방법)	시간복잡도 (V: 노드 수 / E: 엣지 수)
그래프 완전 탐색	재귀함수로 구현	O(V+E)
	스택 자료구조를 이용

 

FILO의 특성을 갖는 스택 자료구조와 재귀함수의 로직이 비슷하다.

따라서 실제 구현 시 재귀함수를 이용하므로 스택 오버 플로우에 유의해야 한다.

 

class DfsSearch{
    public recursive() {
        recursive(); // 재귀 함수
    }
}

위와 같은 재귀 함수에서 함수호출이 깊어질수록 스택 오버플로우가 발생하기 때문에
DFS 구현시 에러를 던지도록 예외 처리 하는것을 반드시 고려해야한다.

 

문제 유형

• 단절점 찾기
• 단절선 찾기
• 사이클 찾기
• 위상 정렬

핵심 이론

• 한번 방문한 노드는 재방문 하지 않음 - `방문배열` 이라고 부르는 방문 여부를 체크할 배열이 필요하다
• LIFO(후입선출)탐색 방식 - 스택 자료구조를 사용한다. (실제로는 스택 성질을 갖는 재귀함수로 구현한다)

탐색시 필요한 구성

• 스택
• 탐색순서
• 인접리스트
• 방문배열

동작 순서

1. 시작노드를 지정하고, 사용할 자료구조(인접리스트)를 초기화한다.
   1. 시작 노드를 지정
   2. 그래프를 인접리스트로 표현
   3. 방문배열을 초기화 (시작노드만 T 나머지는 F)
   4. 스택에 시작노드 삽입
2. 스택에서 노드 출력 후 해당 노드의 인접노드를 다시 스택에 삽입한다.
   1. POP 노드 출력
   2. PEEK 인접리스트에서 꺼낸 인접노드 확인
   3. PUSH 스택에 인접노드 삽입
   4. 방문배열 체크
3. 스택 자료구조에 값이 없을 때 까지 반복한다.
   1 ~ 2 과정을 스택에 값이 더이상 없을 때 까지 반복 (이미 다녀간 노드는 방문 배열을 바탕으로 재삽입 하지 않는것이 핵심)
   스택에 값이 없다는 의미는 시작점 기준 DFS 탐색시 더이상 갈 수 있는곳이 없음을 뜻한다. (DFS 종료)
   
   
   

---

전체 탐색 순서

 

 

[그래프]

1 → 2 → 5 ↓         ↘ 3 → 4 → 6

 

[인접리스트]

1 → 2, 3 2 → 5, 6 3 → 4 4 → 6 5  6

 

[방문 배열]

1	2	3	4	5	6
T	F	F	F	F	F

 

[스택 입출력 순서]

시작노드	3	4	6	5
1	2	2	2	2	6

 

---

 

[스택 데이터 삽입/삭제 순서]

• 스택 마지막 데이터 1 기준
  
  1. 스택에 시작노드 1 출력
  2. 탐색 순서에 1 작성
  3. 방문 배열에 '방문 T' 체크
  4. 인접리스트 인접 노드 2,3 방문배열 방문여부 확인
  5. 2, 3 모두 F이므로 순차적으로 스택에 삽입
     (2, 3 순차적으로 삽입)
• 스택 마지막 데이터 3 기준
  1. 스택 마지막노드 3 출력
  2. 탐색 순서에 3 작성
  3. 방문 배열에 '방문 T' 체크
  4. 인접리스트 인접 노드 4 방문배열 방문여부 확인
  5. 방문여부 F이므로 스택에 4 삽입
     (3 제거 후 4 삽입)
• 마지막 데이터 4 기준
  
  1. 스택 마지막노드 4 출력
  2. 탐색 순서에 4 작성
  3. 방문 배열에 '방문 T' 체크
  4. 인접리스트 인접 노드 6 방문배열 방문여부 확인
  5. 방문여부 F이므로 스택에 6 삽입
     (4 제거 후 6 삽입)

• 마지막 데이터 6 기준
  
  1. 스택 마지막노드 6 출력
  2. 탐색 순서에 6 작성
  3. 방문 배열에 '방문 T' 체크
  4. 인접리스트 인접 노드 없으므로 인접노드 방문여부 생략
     (6 제거)
• 마지막 데이터 2 기준
  
  1. 스택 마지막노드 2 출력
  2. 탐색 순서에 2 작성
  3. 방문 배열에 '방문 T' 체크
  4. 인접리스트 인접 노드 5, 6 방문배열 방문여부 확인
  5. 5와 6 중 5만 F이므로 스택에 5 삽입
     (2 제거 후 5 삽입 순차적으로 삽입)
• 마지막 데이터 5 기준 - 인접리스트  인접노드가 존재하지 않으므로 스택에서 5 제거후 방문배열에 방문여부를 체크
  (5 제거)

 

<탐색 순서 결과>

1 → 3   → 4   → 6  → 2  → 5