⭐️ BFS : Breadth-First Search (너비 우선 탐색) 이란?
출처 : 위키백과 BFS
- 그래프 전체를 탐색하는 하나의 방법으로써, 현재 정점으로부터 가까운 정점들을 먼저 방문한다.
- DFS와 다르게 깊게 파고 드는 것이 아니라, 인접한 정점부터 넓게 탐색한다.
- queue(큐)를 이용해서 구현할 수 있다.
⭐️ BFS의 특징
- 정점 방문 시, 반드시 방문 여부(isVisited)를 검사하고, 방문 시 isVisited를 true로 표시한다.
- 시간 복잡도(Time complexity) : 인접 리스트로 구현 시 O(V+E) // 인접 행렬로 구현 시 O(V^2)
- queue에 다음에 탐색할 정점들을 push하고 pop하는 과정을 거치기 때문에 DFS에 비해서 메모리가 더 필요하다.
- 발견한 경로가 여러 개인 경우에도 최단 경로이며, 발견한 경로가 최단 경로임을 보장한다.
최단 경로가 존재한다면 어느 한 경로가 무한히 깊어져도 최단 경로를 반드시 찾을 수 있다.
- 목표 노드의 깊이가 얕은 경우 DFS보다 더 빠르게 해답을 구할 수 있다.
⭐️ 변수 설명
[이 부분은 이전 포스팅인 DFS (https://m42-orion.tistory.com/63)와 동일합니다!]
그래프를 구현하는 방법에는 인접 리스트를 사용하는 방법과 인접 행렬을 사용하는 방법이 있다.
인접 행렬로 구현하는 방식은 좀 더 직관적이나 시간 복잡도나 공간 복잡도 면에서 비효율적이기 때문에, 인접 리스트로 구현할 것이다.
1. int v, e
v는 정점의 개수, e는 정점 사이를 잇는 간선의 개수이다.
입력받은 정보를 통해 인접 리스트와 방문 여부를 저장하는 변수의 크기를 할당할 수 있다.
2. vector<vector<int>> graph
이중 vector를 사용함으로써 필요한 메모리만 할당해서 사용할 수 있으며, 유동적으로 사용이 가능하다.
먼저 정점의 개수를 입력받은 후 .assign()함수를 이용해서 필요한만큼 할당한다.
// assign 함수를 통해서 vector<int>를 v+1개 할당
graph.assign(v + 1, vector<int>(0, 0));
이후 간선이 연결하는 두 정점을 입력 받으면서, 간선 정보를 graph에 입력한다.
int s, e;
cin >> s >> e; // s : 2, e : 5 일 때
graph[s].emplace_back(e); // graph[2].emplace_back(5);
graph[e].emplace_back(s); // graph[5].emplace_back(2);
3. vector<bool> isVisited
각 노드를 방문했는지의 여부를 저장하는 변수이다.
vector로 선언한 이유는 정점의 개수를 입력 받아서 정점의 개수만큼만 메모리 할당하기 위해서이다.
이렇게 하면 배열의 크기를 미리 크게 정해놓지 않아도 되기 때문에 메모리 공간을 절약할 수 있다.
// 노드는 1번부터 v번까지이고, 아직 어떤 노드도 방문하지 않았기 때문에 false로 초기화
isVisited.assign(v + 1, false);
⭐️ BFS의 진행 단계
1. BFS를 시작할 노드를 정한다. (주로 루트 노드이나 문제에 따라서 달라짐)
2. 시작 노드를 queue에 push하고, 방문 처리를 해준다. (isVisited[start] = true)
3. while문을 시작하는데, 조건을 queue가 완전히 비기 전까지로 설정한다. ( while(!q.empty() )
4. 큐에서 제일 앞에 있는 값을 꺼낸다. 이 값이 이번에 방문하는 노드의 번호이다.
5. 현재 노드(방문하고 있는 노드)의 인접한 노드들을 반복문을 통해 접근한다. 해당 노드를 다음 노드(next)로 설정한다.
6. 다음 노드(next)를 이전에 방문했는지 확인한다.
아직 방문하지 않은 경우에만 해당 노드를 큐에 삽입하고, 방문 처리를 해준다. ( q.push(next); isVisited[next] = true )
7. 4~6의 과정을 모든 노드를 방문할 때까지 && queue가 빌 때까지 반복한다.
⭐️ Queue를 이용한 BFS
위와 같은 그래프가 있다고 했을 때, graph 변수에 양방향 간선 정보를 입력해보자.
그럼 그림 2와 같은 상태가 되었을 것이다.
이제 BFS를 시작해보자.
시작 정점을 루트 노드인 노드 1로 설정하고 BFS를 실행해보자.
while문을 시작하기 전에, 시작 노드를 queue에 삽입하고 방문 처리를 해준다.
그럼 그림3과 같이 queue에는 1만 들어가 있는 상태이고, 1만 방문 처리된 상태일 것이다.
queue에서 원소를 하나 뽑아, 해당 노드를 현재 방문 노드로 설정한다.
이제 1과 인접한 정점들을 하나씩 확인하면서, 아직 방문하지 않은 상태라면 queue에 삽입하고 방문 처리를 한다.
1과 인접한 정점은 graph[1]에 있는 2와 3이다.
두 노드 모두 아직 방문을 하지 않았으므로 두 노드 모두 queue에 삽입하고 방문 처리한다.
다시 queue에서 원소를 하나 뽑고, 해당 노드를 현재 방문 노드로 설정한다. 이번에는 2번 노드가 방문하는 노드이다.
2와 인접한 정점들을 하나씩 확인해보자. graph[2]에 있는 1, 4, 5가 그 대상이다.
1번 노드는 이미 방문했기 때문에 아무 액션을 취하지 않는다.
4번, 5번 노드는 아직 방문하지 않았으므로 두 노드를 queue에 삽입하고 방문 처리한다.
queue에서 원소를 하나 뽑고, 해당 노드를 현재 방문 노드로 설정한다. 이번에는 3번 노드가 방문하는 노드이다.
3과 인접한 정점을 확인해보자. graph[3]에는 1 밖에 없다.
하지만 1번 노드는 이미 방문했기 때문에 아무 액션을 취하지 않고 넘어간다.
queue에서 다시 원소를 하나 뽑고, 해당 노드를 현재 방문 노드로 설정한다. 이번에는 4번 노드가 방문하는 노드이다.
4와 인접한 정점은 2번 노드인데, 2번 노드도 이미 방문했기 때문에 아무 액션을 취하지 않고 넘어간다.
queue에서 원소를 하나 뽑고, 해당 노드를 현재 방문 노드로 설정한다. 이번에는 5번 노드가 방문하는 노드이다.
5와 인접한 정점은 2번, 6번 노드이다.
2번 노드는 이미 방문했기 때문에 아무 액션을 취하지 않고 넘어간다.
반면 6번 노드는 아직 방문하지 않았기 때문에 queue에 삽입하고 방문 처리를 해준다.
이렇게 1번부터 6번까지 모든 노드를 방문 했고, 더 이상 방문할 노드가 없고 queue도 비었기 때문에 BFS를 종료한다.
⭐️ Code
[Parameters]
int v, e; // 정점의 개수, 간선의 개수
vector<vector<int>> graph; // 인접 리스트
vector<bool> isVisited; // 정점 방문 여부 저장
[Method]
void input(){
cin >> v >> e;
// 메모리 공간 할당 및 초기화
graph.assign(v + 1, vector<int> (0, 0));
isVisited.assign(v + 1, false);
for(int i = 0; i < e; i++){
int s, e;
cin >> s >> e;
// 양방향 간선을 연결시킨다.
graph[s].emplace_back(e);
graph[e].emplace_back(s);
}
}
void BFS(int start){
queue<int> q;
q.push(start);
isVisited[start] = true;
while(!q.empty()){
int cur = q.front();
q.pop();
cout << "방문한 노드 : " << cur << '\n';
for(int i = 0; i < graph[cur].size(); i++){
int next = graph[cur][i];
if(!isVisited[next]){
q.push(next);
isVisited[next] = true;
}
}
}
}