📝 깊이 우선 탐색(DFS)이란?
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로 루트 노드나 다른 임의의 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.
🎯 깊이 우선 탐색의 특징
- 모든 노드를 확인하고자 할 때 사용한다.
- 검색 속도는 너비 우선 탐색에 비해 느리다.
- 자기 자신을 호출하는 순환 알고리즘의 형태이다.
- 시간 복잡도
- 인접 리스트로 표현된 그래프 : O(N+E)
- 인접 행렬로 표현된 그래프 : O(N^2)
- 적용 예시) 경로의 특징을 저장할 경우 / 길 찾기 / 미로문제
깊이 우선 탐색 구현 방법
- 탐색 시작 노드를 스택에 삽입하고, 방문 처리한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 위의 1번과 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.
📈 깊이 우선 탐색의 장점
- 현재 경로의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
- 최선의 경우, 가장 빠른 알고리즘으로 운 좋게 항상 해에 도달하는 올바른 경로를 선택한다면, 깊이 우선 탐색이 최소 실행시간에 해를 찾을 수 있다.
- 찾으려는 노드가 깊은 단계에 있다면 BFS보다 빠르게 찾을 수 있다.
📉 깊이 우선 탐색의 단점
- 찾은 해가 최단 경로가 된다는 보장이 없다.
- 최악의 경우, 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해에 도달하는 데 가장 오랜 시간이 걸린다.
📝 너비 우선 탐색(BFS)이란?
가까운 노드부터 탐색하는 알고리즘으로 루트 노드나 다른 임의의 노드에서 시작해서 인접한 노드를 우선적으로 탐색하는 방법이다.
🎯 너비 우선 탐색의 특징
- 두 노드 사이의 최단 경로나 임의의 경로를 찾을 때 사용한다.
- 재귀적 알고리즘이 아니다.
- 자료구조 큐를 사용하여 선입선출을 원칙으로 탐색한다.
- 적용 예시) 길찾기 / 웹 크롤러 / 그래프에서 주변 위치 찾기
너비 우선 탐색 구현 방법
- 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- 위의 1번과 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.
📈 너비 우선 탐색의 장점
- 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에 최단 경로임을 보장한다.
- 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다
- 노드 수가 적고 깊이가 얕은 해가 존재하거나 찾는 노드가 인접할 때 유리하다.
📉 너비 우선 탐색의 단점
- 재귀호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색 할 노드들을 저장하기 때문에 노드의 수가 많을 수록 필요없는 노드들까지 저장하게 되며 메모리를 많이 소비한다.
- 노드의 수가 늘어나면 탐색해야하는 노드가 많아지기 때문에 비효율적이다.
🔗DFS와 BFS 비교
| DFS | BFS | |
|---|---|---|
| 동작원리 | 스택 | 큐 |
| 구현방법 | 재귀 함수 이용 | 큐 자료구조 이용 |
| 공통점 | 그래프의 모든 노드를 탐색 | 그래프의 모든 노드를 탐색 |
참고자료
도라에몽 암기빵