[C++] BFS(Breadth-First Search)

핵심 요약

 

너비 우선 탐색

시작 노드에 인접한 노드들부터 차근차근 탐색하는 알고리즘

간선의 비용이 동일한 최단거리 문제에서 활용된다.

 

 

구현 방식

1. 큐를 사용한다

큐에 노드를 push하고, 방문 처리한다.
노드를 큐에서 pop하고, 인접 노드를 모두 push한 뒤 방문 처리한다.

2. while문의 조건을 통해 모든 노드를 탐색할 때까지 돌린다.

3. while문 안에 for문을 넣어 인접 노드를 탐색한다.

 

 

1. 입력이 배열로 주어질 때

배열에 입력값들을 넣은 뒤, 이동해야 하는 방향(주로 상하좌우)을 탐색한다.

이때, 이동 방향은 dx[4] = {-1, 1, 0, 0} 과 dy[4] = {0, 0, 1, -1}을 이용하여 처리하는 편이다.

이 경우 방문 정보는 bool 형의 2차원 배열로 처리한다.

 

for 반복문에서 이동의 가짓수만큼 반복한다.

 

아래는 백준 1012 유기농 배추 문제로 배열이 입력으로 주어지는 BFS 문제이다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <memory.h>
using namespace std;

struct Pos{
    int x;
    int y;
};

bool visited[55][55];
char map[55][55];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int col, row, k;

void bfs(int startX, int startY){
    queue<Pos> q;

    q.push({startX, startY});
    visited[startY][startX] = true;

    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx >= 0 && nx < col && ny >= 0 && ny < row){
                if(map[ny][nx] == '1' && visited[ny][nx] == false){
                q.push({nx, ny});
                visited[ny][nx] = true;
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin>>t;
    while(t--){
        memset(map, '0', sizeof(map));
        memset(visited, false, sizeof(visited));

        cin>>col>>row>>k;
        for(int i = 0; i < k; i++){
            int x, y;
            cin>>x>>y;
            map[y][x] = '1';
        }

        int cnt = 0;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(map[i][j] == '1' && visited[i][j] == false){
                    bfs(j, i);
                    cnt++;
                }
            }
        }

        cout<<cnt<<"\n";
    }
    return 0;
}

 

2. 입력이 정점과 간선으로 주어질 때

벡터 배열을 이용하여 인접리스트를 구현한다.

vector<int> v[크기]; 와 같이 구성된다.

이 경우 방문 정보는 bool 형의 1차원 배열로 처리한다.

 

for 반복문에서 v[]의 크기만큼 반복한다.

 

아래는 백준 2606 바이러스 문제로 입력이 정점과 간선으로 주어지는 BFS 문제의 답안이다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

vector <int> map[1003];
bool visited[1003];

int bfs(int start){
    int cnt = 0;
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int i = 0; i < map[cur].size(); i++){
            if(visited[map[cur][i]] == false){
                visited[map[cur][i]] = true;
                q.push(map[cur][i]);
                cnt++;
            }
        }
    }

    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin>>n;
    cin>>m;
    for(int i = 0; i < m; i++){
        int u, v;
        cin>>u>>v;
        map[u].push_back(v);
        map[v].push_back(u);
    }

    cout<<bfs(1);
    return 0;
}

 

 

 

구현 방법