[BFS]백준 2606번 바이러스

백준 2606번

바이러스

1번 컴퓨터를 queue에 넣고, 연결된 컴퓨터들 중 아직 감염되지 않은 컴퓨터들을 차례로 queue에 넣어주면 된다. queue가 비게 되면 더 이상 감염시킬 컴퓨터가 없는 것으로 간주하여 끝나게 된다.

간단한 문제였는데, 입력으로 받는 그래프가 양방향 그래프라는 점을 미처 생각하지 못했다.

그래프가 양방향이기 때문에 한 쪽 노드에만 연결 정보를 업데이트하면, 감염 순서에 따라서 잘못된 결과가 나오는 경우가 존재한다.

해당 사례에 대한 반례는 다음과 같다. (양방향 그래프를 고려하지 않은 경우에 대한 반례)

4

4

4 3

1 3

2 4

2 3

output : 1

answer : 3

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

using namespace std;

int main(){
    int com_num,connection;
    cin >> com_num >> connection;
    vector<int> computers[101];
    vector<int> computers_clone[101];
    vector<bool> infected(101,false);
    for(int i=0;i<connection;i++){
        int com1, com2;
        cin >> com1 >> com2;
        computers[com1].push_back(com2);
        computers[com2].push_back(com1);
    }
    queue<int> q;

    q.push(1);
    infected[1]=true;
   int count = 0; 
    while(!q.empty()){
        int infested = q.front();
        q.pop();

        for(int i=0;i<computers[infested].size();i++){
            if(!infected[computers[infested][i]]){
               q.push(computers[infested][i]);
               infected[computers[infested][i]] = true;
              // cout << "infected : " << computers[infested][i] << endl;
               count ++;
            }
        }
    }
    
    cout << count << endl; 
    
}