[c++/알고리즘] 백준 2606 바이러스

corncheese·2021년 8월 2일
0

알고리즘문제풀이

목록 보기
18/31

BFS를 사용한 풀이

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

using namespace std;

// 체크배열 : n번 컴퓨터가 바이러스에 걸렸으면 1로 체크
int ch[101];

int main(){
    int c, l, a, b, x, cnt=0;
    vector<int> V[101];
    queue<int> Q;

    cin >> c >> l;
    
    // 바이러스에 걸린 컴퓨터 네트워크 연결
    for(int i=0; i<l; i++){
        cin >> a >> b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    
    // 1번 컴퓨터부터 체크
    Q.push(1);
    ch[1] = 1;

    while(!Q.empty()){
        x = Q.front();
        Q.pop();
        // 바이러스에 걸린 컴퓨터 숫자세기
        cnt++;

        for(int i=0; i<V[x].size(); i++){
            if(ch[V[x][i]] == 0) {
                ch[V[x][i]] = 1;
                Q.push(V[x][i]);
            }
        }
    }
	
    // 1번 컴퓨터를 제외하고 출력
    cout << cnt-1;
    return 0;
}

0개의 댓글