계발자 블로그
[알고리즘] DFS(Depth-First Search) 깊이 우선 탐색 본문
DFS란?
Depth-First Search의 줄임말로 깊이 우선 탐색이라고 합니다.
그래프 탐색 알고리즘 중 하나로 한 루트로 최대한 깊숙이 들어가서 확인한 뒤
가장 가까운 곳으로 돌아가 다른 루트로 탐색하는 방식입니다.
미로 찾기에서 한 방향으로 끝까지 갔다가 막히면 그곳에서 가장 가까운 갈림길부터 다시 찾는 것입니다.
모든 노드를 방문 하고자 하는 경우에 이 방법을 선택합니다.
특징
- 일반적으로 재귀호출을 사용하여 구현한다.
- 스택이 사용된다.
- 어떤 노드를 방문했었는지 여부를 검사해야 한다
- 그렇지 않을 경우 무한루프에 빠질 수 있다.
- 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
0 - 1 - 3 - 4 - 2 - 5 - 6 순으로 탐색하게 됩니다.
코드로 구현해보기
방문한 순서가 잘 나오는 것을 볼수 있습니다.
'Algorithm' 카테고리의 다른 글
[알고리즘] 선택정렬 (0) | 2022.05.17 |
---|---|
[알고리즘] 에라토스테네스의 체 (0) | 2022.05.16 |
[알고리즘] BFS(Breadth-First Search) 너비 우선 탐색 (0) | 2022.04.20 |
[알고리즘] 피보나치 수열 (0) | 2022.04.09 |
[알고리즘] 재귀함수 (0) | 2022.04.08 |