BFS [c++]

ㅇ 시작 노드와 가까운 순서대로 맹목적 탐색이 이루어진다.

ㅇ 큐를 이용하여 구한다.

ㅇ 사용 예) 미로찾기 등

 

1. 큐에서 하나의 노드를 꺼낸다.

2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

 

아래 코드는 baekjoon 1260번 문제의 양식에 맞게 작성한 코드 이다.

 

// bfs 
#include <iostream>
#include <vector>
#include <queue>  
#include <algorithm>

using namespace std; 

int n,m,startNode; // n : 정점의 개수, m : 이어져있는 노드의 수, startNode : bfs를 시작할 노드

vector<bool> visit; // 방문한 노드를 표시하기 위함 
vector<vector<int>> node; // vector 배열을 받기 위함

void bfs(int start) { 
    queue<int> q; 
    q.push(start);  // 시작점 큐에 넣고
    visit[start] = true;  // 시작점 방문표시
     
    while(!q.empty()) {  // 큐가 비어있지 않으면
        int x = q.front();  // 큐의 front값 x에 저장
        q.pop(); // 큐에서 front를 pop
        printf("%d ", x);  
        for(int i=0; i < node[x].size(); i++) { // 큐의 front였던 노드의 연결점의 개수 만큼 실행 
            int y = node[x][i];  // front의 i번째 연결 점이
            if(visit[y]!= true) {  // 방문하지 않은 노드라면
                q.push(y);   // 큐에 해당 노드 push
                visit[y] = true; // 큐에 해당 노드 방문표시
            } 
        } 
    } 
} 

int main() { 
    int a,b; 
    cin >> n >> m >> startNode; 
    node.resize(n+1); // 1번 인덱스에 1번 노드를 위치시키기 위해 n+1 크기로 할당
    visit = vector<bool>(n + 1, false); // visit를 false로 초기화
    for(int i=0; i<m; i++) { 
        cin >> a >> b; 
        node[a].push_back(b);  // 노드는 양방향 노드라고 가정 했음
        node[b].push_back(a); 
    }

    for (int i = 0; i < node.size(); i++) {  // 노드를 작은 순서대로 정렬
    sort(node[i].begin(), node[i].end());  
    }
    bfs(startNode); 
     
    return 0;     
}

 

 

문제에서 정점 노드가 여러개인 경우 노드 번호가 작은것 부터 방문을 해야 한다고 했으므로

for (int i = 0; i < node.size(); i++) {
sort(node[i].begin(), node[i].end());
}

를 통해 정렬 후에 bfs를 실행해야 올바른 결과를 얻을 수 있다.

cf) sort함수를 사용하기 위해선 algorithm 헤더를 추가해 주자.

 

 

 

ref)  https://www.youtube.com/watch?v=66ZKz-FktXo