[BOJ] #2606 바이러스

https://www.acmicpc.net/problem/2606

2606번: 바이러스

---

BFS를 활용하면 금방 풀리는 문제이다. 입력으로 주어지는 그래프를 인접 리스트 형식으로 구현해놓고, BFS만 돌리면 끝이다. 다만 여기서 포인트는 BFS를 순회하면서 정점들을 기록하는것이 아닌 정점들의 갯수만 카운트 시키고, 마지막 출력할때에 카운트된 변수에서 1만 빼주면 된다. 문제에서 요구하는 출력 조건이 "1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수"이기 때문에 1번 컴퓨터 본인은 제외하고 카운트 해야 하기 때문이다. BFS만 알고있다면 누구나 금방 풀수있는 문제이다.

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

using namespace std;

bool visited[105];
vector<int> Graph[105];
int cnt = 0;

void BFS(int start) {
    queue<int> Q;
    Q.push(start);
    visited[start] = true;

    while(!Q.empty()) {
        int n = Q.front();
        Q.pop();
        cnt++;

        for (int i=0; i<Graph[n].size(); i++) {
            int idx = Graph[n][i];

            if (!visited[idx]) {
                Q.push(idx);
                visited[idx] = true;
            }
        }
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int V, E;
    cin >> V >> E;

    while(E-->0) {
        int x,y;
        cin >> x >> y;

        Graph[x].push_back(y);
        Graph[y].push_back(x);
    }

    BFS(1);

    cout << cnt-1 << '\n';

    return 0;
}