DFS(Depth-First Search)란?
DFS는 깊이 우선 탐색이라고도 불리는, 그래프의 가장 깊은 곳까지 우선적으로 파고들어 탐색을 하게 되는 알고리즘이다.
DFS를 설명하기 전에 먼저 그래프의 기본 구조를 알아야 한다.
그래프는 노드(Node)와 간선(Edge, 종종 정점(Vertex)라고도 불린다)으로 표현되는 일종의 마인드 맵과 같다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말하는데, 이는 길 찾기 및 최단경로 알고리즘 등을 구현하기 위한 기본 원리이다.
두 노드가 간선으로 연결되어 있다면 두 노드가 '인접한다'(Adjacent)라고 표현한다.
DFS는 스택 자료구조를 사용하는데, 따라서 재귀함수를 통해 간단하게 구현할 수 있다. 구현함에 있어 별도의 모듈이 필요없이 list 자료형을 활용하면 되기 때문에 더욱 쉽다.
또한, 필요에 따라(길 찾기 알고리즘인 경우, 현재 진행중인 탐색의 경로의 총 비용)과 함께 다른 리스트에 현재 스택의 정보를 전달하는 식으로의 응용이 가능하다.
DFS의 시간복잡도는 O(N)이다.
DFS의 동작 과정
DFS의 구체적인 동작 과정은 다음과 같다.
1. 탐색 시작 노드를 스택에 삽입하고 "방문 처리"를 한다.
2-1. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 노드를 스택에 넣고 방문 처리를 한다.
2-2. 만약 방문하지 않은 인접 노드가 없다면 최상단 노드를 스택에서 제거한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
여기서 "방문 처리"란 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 말한다. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.
BFS(Breadth-First Search)란?
BFS는 너비 우선 탐색이라고도 불리는, 그래프의 가장 얕은 곳부터 가장 깊은 곳까지 순차적으로 탐색을 하게 되는 알고리즘이다.
BFS는 큐 자료구조를 이용한다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.
너비 우선 탐색 알고리즘인 BFS는 큐 자료구조에 기초한다는 점에서 구현이 간단하다. 따라서 구현할 때 deque 라이브러리를 사용하면 좋으며, BFS의 시간복잡도는 DFS와 마찬가지로 O(N)이다. 그러나 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이다.
BFS의 동작 과정
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤 그 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.