너비 우선 탐색 알고리즘(BFS, Breadth-First Search)

너비 우선 탐색이란?

BFS(Breadth First Search) 알고리즘이란 그래프에서 모든 노드를 탐색하는 2가지 방법 중 인접한 노드를 우선으로 탐색하는 방법이다.

여기서 인접한 노드라는 것을 이해할려면 그래프에 대해서 알고 있어야 한다.

그래프(Graph)란 노드(Node)와 간선(Edge)로 이루어진 자료구조를 의미한다.

 

탐색을 시작할 시작 노드가 결정되면, 시작 노드로부터 한번에 갈 수 있는 노드가 정해져 있다. 이런 노드들을 인접한 노드라고 한다.

즉, 시작 노드에서 바로 갈 수 있는 노드들을 먼저 탐색하고, 그 노드들을 모두 탐색 한 후, 다음 노드로 넘어가게 되는 방식이다.

 

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

BFS와 Queue

BFS는 인접 노드를 먼저 탐색해야 하기 때문에 FIFO(First In First Out) 자료구조인 Queue 자료구조를 사용하게된다.

인접 노드를 Queue에 넣어놓고, Queue에서 빼서 다시 탐색하는 과정을 구현하면 되는 것이다.

 

BFS 구현

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

int x, y;
vector<vector<int>> graph;
vector<vector<bool>> visited;

int BFS(int index);

int BFS(int index) {

    queue<pair<int, int>> q;
    q.push(make_pair(index, 0));

    while(!q.empty()) {

        int node = q.front().first;
        int count = q.front().second;
        q.pop();

        if (isSolution) {
        
            return count;
        }

        for(int i : graph[node]) {
        	
            if(verifyNode(i)){
            	
                visited[node][i] = true;
                q.push(make_pair(i, count + 1));
            }
        }
    }
    return -1;
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int row, col;
    
    cin >> row >> col >> x >> y;
    
    graph.resize(col);
    visited.resize(col, vector<bool> (row, false));
    
    for(int i = 0; i < col; i++) {
    	
        for(int j = 0; j < row; j++) {
        	
            int nextNode;
            cin >> nextNode;
            graph[i].push_back(nextNode);
        }
    }

    cout << BFS(0) << '\n';

    return 0;
}

혹시라도 틀린 내용이 있다면 댓글로 지적해주시면 감사하겠습니다!!