백준[2606] 바이러스

해당 문제는 한 컴퓨터를 통해 바이러스에 감염된 컴퓨터 개수를 파악하는 문제이다.

 

DFS를 통해 계산하면 재귀함수를 이용해서 속도적인 측면에서 느려질 것 같아 BFS를 이용하여 해결했다.

단순 BFS 문제이다.

 

□ 소스 코드

#include <bits/stdc++.h>

int comN,comEdge;
vector<int> viList[101];
bool viVisted[101];
int virusComCnt = 0;

void viFind(int v){
    queue<int> qVirus;
    
    viVisted[v] = true;
    qVirus.push(v);
    
    while(!qVirus.empty()){
        int front = qVirus.front();
        qVirus.pop();
        
        for(int i=0;i<(int)viList[front].size();i++){
            int next = viList[front][i];
            if(!viVisted[next]){
                qVirus.push(next);
                viVisted[next] = true;
                virusComCnt++;
            }
        }
        
    }
    
}

void virus(){
    scanf("%d",&comN);
    scanf("%d",&comEdge);
    
    for(int i=0;i<comEdge;i++){
        int comIn1, comIn2;
        scanf("%d%d",&comIn1,&comIn2);
        viList[comIn2].push_back(comIn1);
        viList[comIn1].push_back(comIn2);
    }
    
    viFind(1);
    printf("%d\n",virusComCnt);
}