[Algorithm] DFS
너비 우선 탐색(Breadth-First Search)란?
DFS는 그래프 탐색 알고리즘 중 하나로, 그래프의 한 분기(branch)를 끝까지 탐색한 후, 이전 분기점으로 돌아가 다른 분기를 탐색하는 방식입니다. 미로 찾기, 경로 탐색, 사이클 찾기 등 다양한 문제 해결에 활용됩니다.
(출처 : illinois.edu)
동작방식
- 시작 정점을 방문합니다.
- 시작 정점에 인접한 정점 중 하나를 선택하여 방문합니다.\
- 선택한 정점에 인접한 정점 중 아직 방문하지 않은 정점을 선택하여 방문하는 과정을 반복합니다.
- 더 이상 방문할 수 있는 인접한 정점이 없을 경우, 이전 정점으로 돌아갑니다 (Backtracking).
- 모든 정점을 방문할 때까지 위 과정을 반복합니다.
DFS의 특징
- 스택(Stack) 또는 재귀 호출 사용: 탐색 경로를 저장하고 이전 정점으로 돌아가기 위해 스택 자료구조를 사용하거나, 재귀 호출을 통해 구현합니다.
- 경로 탐색, 사이클 탐색 등에 유용: 그래프 내의 경로를 찾거나, 사이클 존재 여부를 확인하는 데 효과적입니다.
- 구현이 비교적 간단: BFS에 비해 구현이 간결한 경우가 많습니다 (특히 재귀 호출 사용 시).
DFS의 활용 예시
- 경로 탐색: 미로 찾기, 특정 경로 존재 여부 확인
- 사이클 탐색: 그래프 내 사이클 존재 여부 확인
- 위상 정렬 (Topological Sort): 작업의 순서를 정하는 문제
- 연결 요소 찾기 (Connected Components): 그래프에서 연결된 부분 그래프 찾기
- 백트래킹 (Backtracking): 모든 가능한 경우를 탐색하는 문제 (N-Queens 문제, 스도쿠 풀이 등)
장단점
장점
- 메모리 사용량 절약: BFS는 큐를 사용하여 탐색할 정점들을 저장하는 반면, DFS는 스택 또는 재귀 호출을 사용하여 현재 경로의 정점들만 저장하면 됩니다. 따라서, 그래프의 규모가 크고 깊이가 깊은 경우 BFS보다 메모리 사용량이 적습니다. 특히, 탐색해야 할 정점의 수가 매우 많거나, 그래프의 깊이가 무한정 깊어질 수 있는 경우에 유리합니다.
- 구현이 비교적 간단: 특히 재귀 호출을 사용하는 경우, 코드가 간결하고 직관적입니다. 스택을 직접 사용하는 경우에도 BFS에 비해 구현이 간단한 편입니다.
- 경로 탐색, 사이클 탐색 등에 효율적: 특정 경로를 찾거나, 그래프 내의 사이클 존재 여부를 확인하는 데 효과적입니다. 백트래킹(Backtracking) 알고리즘의 기본이 되는 탐색 방법이기도 합니다.
- 목표 정점이 깊은 단계에 있는 경우 해를 빨리 구할 수 있음: 만약 목표 정점이 탐색 시작점에서 멀리 떨어져 있고, 그래프의 깊이가 깊다면, BFS보다 DFS가 더 빨리 목표 정점에 도달할 수 있습니다.
단점
- 최단 경로 보장 X: BFS는 가중치가 없는 그래프에서 최단 경로를 보장하지만, DFS는 최단 경로를 보장하지 않습니다. 목표 정점에 도달하는 여러 경로 중 하나를 찾을 수는 있지만, 그 경로가 반드시 최단 경로라는 보장은 없습니다. 최단 경로를 찾아야 하는 경우에는 BFS를 사용하는 것이 적합합니다.
- 해가 없는 경로가 깊을 경우 탐색 시간이 오래 걸릴 수 있음: 만약 탐색해야 하는 그래프에 해가 없는 깊은 경로가 존재할 경우, DFS는 그 경로를 끝까지 탐색하느라 시간을 낭비할 수 있습니다. 이러한 경우 탐색 깊이를 제한하는 등의 추가적인 처리가 필요할 수 있습니다.
- 스택 오버플로우 발생 가능성 (재귀 사용 시): 재귀 호출을 사용하여 DFS를 구현하는 경우, 그래프의 깊이가 매우 깊으면 스택 오버플로우가 발생할 수 있습니다. 이러한 경우에는 스택을 직접 사용하여 DFS를 구현하거나, 탐색 깊이를 제한하는 등의 방법을 고려해야 합니다.
예제
#include <iostream>
#include <vector>
#include <list>
using namespace std;
class Graph {
private:
int numVertices;
vector<list<int>> adj;
public:
Graph(int vertices) : numVertices(vertices), adj(vertices) {}
void addEdge(int u, int v) {
adj[u].push_back(v); // 방향 그래프
// adj[v].push_back(u); // 무방향 그래프의 경우 추가
}
void DFSUtil(int v, vector<bool>& visited) { // DFS를 위한 유틸리티 함수 (재귀)
visited[v] = true; // 현재 정점 방문 처리
cout << v << " "; // 방문한 정점 출력
// 현재 정점에 인접한 정점들을 방문
for (int neighbor : adj[v]) {
if (!visited[neighbor]) { // 아직 방문하지 않은 정점인 경우
DFSUtil(neighbor, visited); // 재귀 호출
}
}
}
void DFS(int startVertex) {
vector<bool> visited(numVertices, false); // 방문 여부 저장
DFSUtil(startVertex, visited); // DFS 시작
cout << endl;
}
};
int main() {
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);
cout << "Starting DFS from vertex 0: ";
g.DFS(0); // 0번 정점에서 DFS 시작
return 0;
}