백준 2606 바이러스, c++

 

 

 

작성한 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
 
vector<int> vec[101];
vector<int> result_bfs;
bool visit[101];
 
void bfs(int temp){
    queue<int> q;
    q.push(temp);
    visit[temp] = true;
    
    while(!q.empty()){
        int x = q.front();
        q.pop();
        result_bfs.push_back(x);
 
        for (int i = 0; i < vec[x].size(); i++){
            if(!visit[vec[x][i]]){ //방문하지 않은 곳만 탐색
                q.push(vec[x][i]); 
                visit[vec[x][i]] = true;
            }
        }
    }
}
 
int main(){
    int n, m, a, b;
    cin >> n;
    cin >> m;
 
    for (int i=1; i<=m; i++){
        cin >> a >> b;
        vec[a].push_back(b); //양방향 간선처리
        vec[b].push_back(a); //양방향 간선처리
    }
   
    bfs(1);
    
    cout << result_bfs.size()-1;
    
    return 0;
}

 

1번 정점부터 시작해 1번과 연결된 모든 정점의 개수를 구하는 문제였다.

따라서 그냥 bfs 알고리즘을 통해 탐색하며 거치는 모든 정점의 개수를 count하면 되는 문제였다.