BFS 알고리즘 이란?
DFS 설명 보려면 이전 글을 참고하자
BFS(Breadth-First Search) 는 DFS와 더불어 그래프에서 많이 사용하는 알고리즘이다.
체감상 DFS보다 BFS를 사용하는 문제를 더 많이 접하게 되는 것 같다.
DFS와 마찬가지로 BFS 알고리즘은 한 노드에서 출발해 연결된 모든 노드들을 방문하게 된다.
하지만 DFS가 가능한 한 깊게 탐색하고 되돌아 오는 것에 반해 BFS는 가까운 모든 노드들을 먼저 방문한 후 깊이 들어가게 된다.
BFS 알고리즘 작동 방식
BFS 알고리즘이 어떻게 작동하는지 살펴보자
BFS는 큐(Queue) 자료구조를 사용해서 구현한다
- 큐 초기화
- 시작 노드 방문
- 인접 노드 큐에 추가
- 큐가 빌때까지 반복
DFS를 설명했던 노드 그림을 그대로 가져와서 설명해 보도록 하겠다.
- 큐 초기화
시작 노드는 0으로 설정하였다.
Queue : [0]
Queue : [1, 2]
2. 시작 노드 방문
3. 인접노드 큐에 추가
큐에서 시작노드 0을 뺀 후 0과 연결되어 있는 모든 노드들을 큐에 추가한다.
여기서는 1, 2가 연결되어 있기 때문에 queue에는 0, 1이 들어가게 된다.
4. 큐에 없어질때까지 반복
노드 1 방문
Queue : [2, 3]
큐는 FIFO로 먼저들어간 1이 먼저 나오게 된다.
1을 방문한 후 1과 연결된 노드들을 모두 추가해 준다.
여기서는 3이 있기 때문에 큐에 3을 넣어 준다.
노드 2 방문
Queue : [3, 4, 5]
큐의 제일 앞에 있는 2를 빼서 방문한다.
2와 연결되어 있는 노드들을 모두 큐에 넣는다.
여기서는 4, 5가 연결되어 있기 때문에 큐는 원래 있던 3과 4, 5가 추가된다.
노드 3 방문
Queue : [4, 5]
큐의 제일 앞에 있는 3을 꺼내어 방문한다.
3에는 더이상 연결되어 있는 노드가 없기 때문에 아무것도 추가하지 않는다.
노드 4 방문
Queue : [5]
큐의 제일 앞에 있는 4를 꺼내어 방문한다.
4도 더이상 연결되어 있는 노드가 없기 때문에 추가하지 않는다.
노드 5 방문
Queue : []
큐의 제일 앞에 있는 5를 꺼내어 방문한다.
더이상 추가할 노드가 없고, 큐도 비었기 때문에 BFS를 종료하게 된다.
결론
BFS 알고리즘 ( 너비 우선 탐색)은 주변 노드들을 먼저 탐색하기 때문에
0 -> 1 -> 2 -> 3 -> 4 -> 5의 순서대로 탐색하게 된다.
어떤 문제에서 BFS를 써야하는가
BFS는 활용도가 무궁무진하다고 생각한다.
그리고 그 중에 많이 쓰이는 것들을 몇개 추려 보았다
- 최단 경로 찾기 (노드 간, 2차원)
- 바이러스 문제
- 미로찾기
대부분의 문제 유형이 비슷한 느낌인데
그래프 문제에서 주로 최단경로, 적절한 길을 찾는 문제에 많이 사용한다고 생각하면 될 것 같다.
최단 경로에서 BFS가 유용한 이유는 BFS 알고리즘이 현재 노드의 인접 노드들을 하나씩 모두 확인하기 때문에 가장 먼저 찾아지는 경로가 곧 최단거리이기 때문이다!!
BFS 알고리즘 장단점 / 시간복잡도
장점
- 최단경로를 보장한다
- 알고리즘이 꽤 간단하다
단점
- 메모리 소모가 크다
- 비효율적이다.
최단경로를 찾을 수는 있지만 그래프의 크기가 매우 클 경우 메모리 소모가 크고 최악의 비효율적일 수 있다. 따라서 그래프의 크기가 크다면 dfs를 사용하는 것이 더 맞다.
시간복잡도
노드 수 (V), 간선 수 (E) 일때
O(V+E)의 시간복잡도를 가진다.
C++ BFS 알고리즘 구현
BFS 알고리즘을 #include <queue> 헤더를 사용해서 구현하면 간단하게 할 수 있다.
DFS와 마찬가지로 visited 배열이 있어야 하고
각 노드에 방문할 때마다 visited 배열을 true로 만들고 연결된 노드들을 큐에 넣어 준다.
그리고 큐가 빌때까지(모두 방문할때까지) while문을 돌리며 반복한다.
void BFS(int V, vector<int> adj[], int s) {
vector<bool> visited(V, false);
queue<int> queue;
visited[s] = true;
queue.push(s);
while(!queue.empty()) {
s = queue.front();
cout << s << " ";
queue.pop();
for (int i = 0; i < adj[s].size(); i++) {
if (!visited[adj[s][i]]) {
visited[adj[s][i]] = true;
queue.push(adj[s][i]);
}
}
}
}
전체적인 방법은 DFS와 비슷한 것 같다.
단지 queue냐 stack이냐의 차이로 구현하면 될 것 같다.
