[백준] 2606 바이러스

백준2606링크

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력

풀이

1번 노드와 이어져 있는 노드의 수 구하기 -> BFS/DFS로 풀이 가능

• BFS
  

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

using namespace std;

int N,M;
int virus=0;
bool visited[101]={false,};
vector<int> g[101];
queue<int> q;

void BFS(int start){
    visited[start]=true;
    
    while(!q.empty()){
        int next=q.front();
        q.pop();
        
        //next노드와 이어져 있는 노드(방문되지 않은)들을 큐에 넣기
        for(int i=0;i < g[next].size();i++){
            if(!visited[g[next].at(i)]){
                virus++;
                q.push(g[next].at(i));
                visited[g[next].at(i)]=true;
            }
        }
    }
    return;
}

int main() {
    cin>>N;
    cin>>M;
    
    int a,b;
    for(int i=0;i < M;i++){
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    
    q.push(1);
    BFS(1);
    
    cout<<virus<<"\n";
    
    return 0;
}