BFS : 너비 우선 탐색
- 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- Brute Force(완전 탐색) 알고리즘
- 큐를 활용해 구현
BFS의 효용성
- 일반적인 상황에서 DFS는 BFS의 기능으로 모두 대체 가능
- 일반적인 상황에서 트리의 높이를 리턴하는 BFS의 특성상 BFS가 DFS보다 유용하다.
- 단, 그래프와 트리에서 DFS가 유용해진다.
- BFS 장점
- 출발 노드에서 목표 노드까지 최단 길이 보장
- BFS 단점
- 경로가 매우 길 경우 탐색 분기가 급격히 증가해 많은 저장 공간 필요
- 유한 그래프: 모든 그래프를 탐색한 후 실패 리턴하므로, 시간 낭비
- 무한 그래프: 해를 찾지 못하고, 탐색 종료 불가
- 즉, 그래프는 DFS로 풀어야 한다.
BFS 구현 방법
- 탐색 시작 노드를 큐에 삽입하고, 방문 처리
- 큐에서 노드를 꺼낸 뒤 인접 노드 중 방문하지 않은 노드를 '모두' 큐에 삽입하고 망문 처리
- 2번 과정을 수행할 수 없을 때까지 반복
BFS <-> DFS
- 다차원 배열에서 BFS가 큐로 구현된 경우 적용 가능
- 큐를 스택으로 바꾸면 DFS가 된다.
BFS 사용 예제
1. 그래프 BFS 사용 예제
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool visited[9];
vector<int> graph[9];
// BFS 함수 정의
void bfs(int start) {
queue<int> q;
q.push(start);
// 현재 노드를 방문 처리
visited[start] = true;
// 큐가 빌 때까지 반복
while(!q.empty()) {
// 큐에서 하나의 원소를 뽑아 출력
int x = q.front();
q.pop();
cout << x << ' ';
// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for(int i = 0; i < graph[x].size(); i++) {
int y = graph[x][i];
if(!visited[y]) {
q.push(y);
visited[y] = true;
}
}
}
}
int main(void) {
// 노드 1에 연결된 노드 정보 저장
graph[1].push_back(2);
graph[1].push_back(3);
graph[1].push_back(8);
// 노드 2에 연결된 노드 정보 저장
graph[2].push_back(1);
graph[2].push_back(7);
// 노드 3에 연결된 노드 정보 저장
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
// 노드 4에 연결된 노드 정보 저장
graph[4].push_back(3);
graph[4].push_back(5);
// 노드 5에 연결된 노드 정보 저장
graph[5].push_back(3);
graph[5].push_back(4);
// 노드 6에 연결된 노드 정보 저장
graph[6].push_back(7);
// 노드 7에 연결된 노드 정보 저장
graph[7].push_back(2);
graph[7].push_back(6);
graph[7].push_back(8);
// 노드 8에 연결된 노드 정보 저장
graph[8].push_back(1);
graph[8].push_back(7);
bfs(1);
}2. 큐 BFS 사용 예제
void bfs(int x, int N){
queue<int> q;
check[x] = true;
q.push(x);
while(q.empty()){
int x = q.front();
q.pop();
for(int i = 1; i <= N; ++i){
if(arr[x][i] == true && check[i] == false){
check[i] = true;
q.push(i);
}
}
}
}3. 큐 BFS 사용 예제
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502] =
{{1,1,1,0,1,0,0,0,0,0},
{1,0,0,0,1,0,0,0,0,0},
{1,1,1,0,1,0,0,0,0,0},
{1,1,0,0,1,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0} }; // 1이 파란 칸, 0이 빨간 칸에 대응
bool visited[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // n = 행의 수, m = 열의 수
// 상하좌우 네 방향을 의미
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
queue<pair<int,int>> Q;
visited[0][0] = 1; // (0, 0)을 방문했다고 명시
Q.push({0,0}); // 큐에 시작점인 (0, 0)을 삽입.
while(!Q.empty()){
pair<int,int> cur = Q.front();
Q.pop();
cout << '(' << cur.X << ", " << cur.Y << ") -> ";
for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감
if(visited[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우 넘어감
visited[nx][ny] = 1; // (nx, ny)를 방문했다고 표시
Q.push({nx,ny});
}
}
}
GAME DESIGN & CLIENT PROGRAMMING