개발자공부일기
DFS, BFS 본문
그래프 탐색 알고리즘
그래프 탐색 알고리즘은 그래프 구조에서 특정 노드나 경로를 찾기 위해 사용되는 알고리즘입니다. 대표적인 그래프 탐색 알고리즘으로는 깊이 우선 탐색(DFS, Depth-First Search)과 너비 우선 탐색(BFS, Breadth-First Search)이 있습니다.
그래프 탐색 알고리즘은 그래프 구조에서 특정 노드나 경로를 찾기 위해 사용됩니다.
DFS와 BFS는 각각의 탐색 방식과 특성이 다르기 때문에, 문제의 특성에 따라 적절한 알고리즘을 선택하여 사용해야 합니다. DFS는 깊이 우선으로 탐색을 진행하며, BFS는 너비 우선으로 탐색을 진행합니다.
DFS 깊이 우선 탐색 (Depth-First Search)
깊이 우선 탐색(DFS)은 그래프의 한 노드에서 시작하여 가능한 한 깊이 내려가면서 탐색을 진행하는 알고리즘입니다. DFS는 스택 자료구조를 사용하여 구현할 수 있으며, 재귀적으로도 구현할 수 있습니다.
예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있습니다.
- 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
- 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림
#include <iostream>
#include <vector>
using namespace std;
class GraphDFS {
int V; // 정점 개수
vector<vector<int>> adj; // 인접 리스트
public:
GraphDFS(int V) {
this->V = V;
adj.resize(V);
}
void addEdge(int v, int w) {
adj[v].push_back(w);
adj[w].push_back(v); // 무방향 그래프
}
void DFSUtil(int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
for (int u : adj[v]) {
if (!visited[u]) {
DFSUtil(u, visited);
}
}
}
void DFS(int start) {
vector<bool> visited(V, false);
DFSUtil(start, visited);
cout << endl;
}
};
int main() {
GraphDFS g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
cout << "DFS 탐색: ";
g.DFS(0);
return 0;
}BFS 너비 우선 탐색 (Breadth-First Search)
너비 우선 탐색(BFS)은 그래프의 한 노드에서 시작하여 인접한 노드를 먼저 탐색한 후, 그 다음 인접한 노드를 탐색하는 방식으로 진행하는 알고리즘입니다. BFS는 큐 자료구조를 사용하여 구현할 수 있습니다.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택합니다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class GraphBFS {
int V; // 정점 개수
vector<vector<int>> adj; // 인접 리스트
public:
GraphBFS(int V) {
this->V = V;
adj.resize(V);
}
void addEdge(int v, int w) {
adj[v].push_back(w);
adj[w].push_back(v); // 무방향 그래프
}
void BFS(int start) {
vector<bool> visited(V, false);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
cout << v << " ";
for (int u : adj[v]) {
if (!visited[u]) {
visited[u] = true;
q.push(u);
}
}
}
cout << endl;
}
};
int main() {
GraphBFS g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
cout << "BFS 탐색: ";
g.BFS(0);
return 0;
}
| DFS(깊이우선탐색) | BFS(너비우선탐색) |
| 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 | 현재 정점에 연결된 가까운 점들부터 탐색 |
| 스택 또는 재귀함수로 구현 | 큐를 이용해서 구현 |
DFS와 BFS의 시간복잡도
두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일합니다.
DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 됩니다.
깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용
DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.
- 그래프의 모든 정점을 방문하는 것이 주요한 문제
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.
둘 중 편한 것을 사용하시면 됩니다. - 경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다) - 최단거리 구해야 하는 문제
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.
이밖에도
- 검색 대상 그래프가 정말 크다면 DFS를 고려
- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
라이브러리 설명
vector 라이브러리
#include <vector>는 동적 배열을 제공하는 C++ 표준 라이브러리다.
vector는 자동으로 크기가 조절되며, 배열처럼 요소에 접근할 수 있다.
사용한 vector 함수 및 기능
- vector<int> adj[V];
→ 정점 개수 V만큼의 벡터 배열을 생성해서, 각 정점이 연결된 다른 정점들을 저장할 수 있도록 함. - adj.resize(V);
→ 벡터의 크기를 V로 조정해서 정점 개수만큼 공간을 확보함. - adj[v].push_back(w);
→ 정점 v에서 w로 가는 간선을 추가함. 무방향 그래프라면 w에서도 v로 가는 간선도 추가해야 함. - for (int u : adj[v])
→ 정점 v에 연결된 모든 정점을 하나씩 꺼내서 반복문을 돌리는 방식. (range-based for 문법 사용)
queue 라이브러리
#include <queue>는 FIFO(First-In-First-Out) 구조의 큐를 제공한다.
BFS에서 방문할 정점을 순서대로 저장하는 데 사용된다.
사용한 queue 함수
- queue<int> q;
→ 정수를 저장하는 큐를 선언함. - q.push(v);
→ 정점 v를 큐에 추가함. (다음 방문할 정점) - q.front();
→ 큐의 맨 앞 원소를 반환함. (삭제하지 않고 확인) - q.pop();
→ 큐의 맨 앞 원소를 제거함. - q.empty();
→ 큐가 비어 있는지 확인해서 탐색이 끝났는지 판단함. (true or false 반환)
