DFS(Depth-First Search)란?
깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.
'방문 처리'는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다. DFS를 이용하여 탐색하면 일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개있으면 번호가 낮은 순서부터 처리한다.
아래와 같은 그래프를 예를 들어 노드 1을 시작으로 DFS 알고리즘 이용하여 탐색을 진행 해보자.
[step 1] 시작 노드인 '1'을 스택에 삽입하고 방문 처리를 한다.
[step 2] 스택의 최상단 노드인 '1'에 방문하지 않은 인접노드 '2', '3', '8'이 있다. 이중에서 가증 작은 노드 '2'를 스택에 넣고 방문처리한다.
[step 3] 스택의 최상단 노드인 '2'에 방문하지 않은 인접 노드 '7'이 잇다. 따라서 '7'번 노드를 스택에 넣고 방문 처리를 한다.
[step 4] 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '6'과 '8'이 있다. 이 중에서 가장 작은 노드인 '6'을 스택에 넣고 방문 처리를 한다.
[step 5] 스택의 최상단 노드인 '6'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '6'번 노드를 꺼낸다.
[step 6] 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '8'이 있다. 따라서 '8'번 노드를 스택에 넣고 방문 처리를 한다.
[step 7] 스택의 최상단 노드인 '8'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '8'번 노드를 꺼낸다.
[step 8] 스택의 최상단 노드인 '7'에 방문하지 않은 인접노드가 없다. 따라서 스택에서 '7'번 노드를 꺼낸다.
[step 9] 스택의 최상단 노드인 '2'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '2'번 노드를 꺼낸다.
[step 10] 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 '3'을 스택에 넣고 방문 처리한다.
[step 11] 스택의 최상단 노드인 '3'에 방문하지 않은 인접 노드 '4'와 '5'가 있다. 이 중에서 가장 작은 노드인 '4'를 스택에 넣고 방문 처리한다.
[step 12] 스택의 최상단 노드인 '4'에 방문하지 않은 인접 노드 '5'가 있다. 따라서 '5'번 노드를 스택에 넣고 방문 처리를 한다.
[step 13] 남아 있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 다음과 같다.
결과적으로 노드의 탐색 순서는 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5 이다.
깊이 우선 탐색 알고리즘인 DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N개의 경우 O(N)의 시간이 소요된다.
DFS 알고리즘 예제
https://developercc.tistory.com/11
[탐색 알고리즘 DFS 깊이 우선 탐색] 예제 자바 코드 (코딩 테스트, 코딩 면접 준비)
탐색 알고리즘 DFS 깊이 우선 탐색 개념 정리는 아래 링크 참조 https://developercc.tistory.com/10 탐색 알고리즘 DFS 깊이 우선 탐색 [코딩 테스트, 코딩 면접 준비] DFS(Depth-First Search)란? 깊이 우선 탐..
developercc.tistory.com
References
「이것이 코딩테스트다」 - 한빛미디어 (나동빈 저)
BFS(Breath First Search) 너비 우선 탐색 알고리즘 알고싶다면?
https://developercc.tistory.com/13
탐색 알고리즘 BFS 너비 우선 탐색 [코딩 테스트, 코딩 면접 준비]
BFS(Breath First Search)란? 너비 우선 탐색이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘이다. DFS(Depth First Search)는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 BFS는 그 반대이다. BF
developercc.tistory.com
'알고리즘' 카테고리의 다른 글
| [탐색 알고리즘 BFS 너비 우선 탐색] 예제 자바 코드 (코딩 테스트, 코딩 면접 준비) (0) | 2021.07.04 |
|---|---|
| 탐색 알고리즘 BFS 너비 우선 탐색 [코딩 테스트, 코딩 면접 준비] (0) | 2021.06.27 |
| [탐색 알고리즘 DFS 깊이 우선 탐색] 예제 자바 코드 (코딩 테스트, 코딩 면접 준비) (0) | 2021.06.21 |
| 탐욕 (그리디) 알고리즘 [코딩 테스트, 코딩 면접 준비] (0) | 2021.06.19 |
| 알고리즘 시간 복잡도(Complexity) 쉽게 이해하기 (0) | 2021.06.14 |
