DFS/BFS 는 그래프 자료구조에 기반한 대표적인 '탐색' 알고리즘이다.
그래프 탐색 순서에 따라 DFS 와 BFS 가 구분된다.
💡 그래프 탐색 알고리즘
그래프는 정점과 간선으로 이루어진 자료구조의 일종이다.
그래프 탐색 알고리즘이란 한 정점에서 시작하여 차례대로 그래프에 있는 모든 정점들은 한번씩 방문하는 알고리즘을 뜻한다.
많은 그래프에 대한 문제를 해결하기 위해서 그래프 탐색 알고리즘을 알아야하는데 예를들어 다음과 같은 상황에서 탐색이 필요하다.
- 한 정점과 다른 정점의 경로를 구할 때
- 그래프가 연결되어 있는지 확인할 때
- 신장 트리(Spanning Tree)를 찾을 때
💡 깊이 우선 탐색(DFS - Depth-First Search)
DFS 는 한국어로 '깊이 우선 탐색' 이라고 불리며, '스택' 자료구조를 사용한 그래프 탐색 알고리즘이다.
이름에서 알 수 있듯, 루트 노드에서 시작하여 다른 분기 (Branch) 로 넘어가기 전, 현재 탐색중인 분기를 완벽하게 (깊게) 탐색하는 방식이다.
가장 깊은 노드까지 도달하였을 때 탐색한 경로를 역추적하여 되돌아나오기 위해 스택을 사용한다.
또한 이미 방문한 노드를 다시 방문하지 않기 위해 방문한 노드를 따로 저장을 해야한다. 이를 '방문 처리' 라고 한다.
DFS 의 동작 순서를 정리하면 아래와 같다.
- 루트 노드를 스택에 넣고 방문처리 한다.
- 스택 최상단 노드의 인접 노드 중 방문하지 않은 노드 하나를 스택에 넣고 방문처리한다. 만약 인접 노드를 모두 방문한 경우 스택을 Pop 한다.
- 2 단계를 더 이상 수행할 수 없을 때 까지 (스택이 빌 때 까지) 반복한다.
DFS 동작 방식 예시
- Step 1 : 탐색시작 노드인 1번 노드 방문처리 [1]
- Step 2 : 1번 노드의 인접 노드(2) 방문처리 [1,2]
- Step 3 : 2번 노드의 인접 노드(3) 방문처리 [1,2,3]
- Step 4 : 3번 노드의 인접 노드가 없으므로 꺼냄 [1,2]
- Step 5 : 2번 노드의 인접 노드가 없으므로 꺼냄 [1]
- Step 6 : 1번 노드의 인접 노드(4) 방문처리 [1,4]
- Step 7 : 4번 노드의 인접 노드(5) 방문처리 [1,4,5]
- Step 8 : 5번 노드의 인접 노드가 없으므로 꺼냄 [1,4]
- Step 9 : 5번 노드의 인접 노드가 없으므로 꺼냄 [1]
- Step 10 : 1번 노드의 인접 노드(6) 방문처리 [1,6]
- Step 11 : 6번 노드의 인접 노드가 없으므로 꺼냄 [1]
- Step 12 : 1번 노드의 인접 노드가 없으므로 꺼냄 []
DFS의 장/단점
- 장점
- 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다.
- 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
- 단점
- 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다.
- 얻어진 해가 최단 경로가 된다는 보장이 없다.
- 깊이가 무한히 깊어지면 스택오버플로우가 날 위험이 있다. (깊이 제한을 두는 방법으로 해결가능)
💡 너비 우선 탐색(BFS - Breadth-First Search)
BFS 는 한국어로 '너비 우선 탐색' 이라고 불리며, '큐' 자료구조를 사용한 그래프 탐색 알고리즘이다.
이름에서 알 수 있듯, 현재 노드와 가까운 노드를 우선적으로 넓게 탐색하는 방식이다.
현재 노드의 이웃 노드를 스택이 아닌 큐에 집어넣어 자연스럽게 먼저 들어간 노드를 먼저 탐색 (FIFO) 하게 되는 방식이다.
BFS 의 동작 순서를 정리하면 아래와 같다.
- 루트 노드를 큐에 넣고 방문처리한다.
- 큐를 Deque 하고, Deque 한 노드의 방문하지 않은 모든 인접 노드를 큐에 넣고 방문 처리한다.
- 2 단계를 더 이상 수행할 수 없을 때 까지 (큐가 빌 때 까지) 반복한다.
BFS 동작 방식 예시
- Step 1 : 탐색시작 노드인 1번 노드 방문처리 [1]
- Step 2 : 1번 노드를 꺼내고 모든 인접 노드(2,4,6) 방문처리 [2,4,6]
- Step 3 : 2번 노드를 꺼내고 모든 인접 노드(3) 방문처리 [4,6,3]
- Step 4 : 4번 노드를 꺼내고 모든 인접 노드(5) 방문처리 [6,3,5]
- Step 5 : 6번 노드를 꺼내고 인접 노드가 없어 Pass [3,5]
- Step 6 : 3번 노드를 꺼내고 인접 노드가 없어 Pass [5]
- Step 7 : 5번 노드를 꺼내고 인접 노드가 없어 Pass []
BFS의 장/단점
- 장점
- 너비를 우선으로 탐색하므로 답이 되는 경로가 여러 개인 경우에도 최단경로를 얻을 수 있다.
- 경로가 무한히 깊어져도 최단경로를 반드시 찾을 수 잇다.
- 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리하다.
- 단점
- DFS와 달리 큐를 이용하여 다음에 탐색할 정점들을 저장하므로 더 큰 저장공간이 필요하다.
DFS와 BFS 비교
깊이 우선 탐색(DFS)
- 동작원리 : 스택
- 구현방법 : 재귀 함수 이용
- 장단점 :
- 그래프의 깊이(depth)가 깊을 수록 빠름
- 메모리가 적음
- 적용 :
- 경로의 특징을 저장해야 하는 경우
- 길 찾기
- 미로 문제
너비 우선 탐색(BFS)
- 동작원리 : 큐
- 구현방법 : 큐 자료구조 이용
- 장단점 :
- 찾는 노드가 인접할 때 유리
- 노드가 많을 수록 메모리를 많이 소비
- 적용 :
- 길 찾기, 라우팅
- 웹 크롤러
- 소셜 네트워크에서 멀리 떨어진 사람 찾기
- 그래프에서 주변 위치 찾기
DFS와 BFS의 시간복잡도
두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.
둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.
N : 노드 / E : 간선
인접 리스트 : O(N+E)
인접 행렬 : O(N^2)
일반적으로 E(간선)의 크기가 N^2에 비해 상대적으로 적기 때문에 인접 리스트 방식이 효율적이다.
인접 행렬의 경우, 정점의 개수 N만큼 도는 이중 for문을 돌려 두 정점 간에 간선이 존재하는지를 확인해야한다.
이때 N의 제곱만큼 돌게 되므로 O(N^2)의 시간 복잡도가 된다.
인접 리스트로 구현된 경우, 존재하는 간선의 정보만 저장되어 있으므로 인접 행렬에서 사용한 이중 for문이 필요하지 않다.
다음 노드가 방문하였는지 확인할 때 간선의 개수인 E의 두 배만큼 시간이 걸리고(1번에서 2,6번이 방문하였는지를 확인하고 2번에서 1,3,6번을 방문하였는지 확인한다. 이 때 1번과 2번의 간선 하나에 두 번의 확인을 하기 때문에 두배만큼 시간이 걸린다.) 각 노드를 방문할 때 정점의 개수인 N만큼 걸린다. 따라서 O(N+2*E) = O(N+E)가 된다. (시간 복잡도에서 계수는 삭제)