[백준 2606] 바이러스

풀이

컴퓨터를 어떻게 코드 상으로 연결할지 생각하자.

이 문제에서는 주어진 간선만 표현하면 되므로 인접 리스트가 편하다.

이때 주의할 점은 양방향 간선으로 그래프를 표현해야 한다.

 

바이러스의 전파는 무조건 컴퓨터 1번으로부터 시작하므로 1번부터 인접한 컴퓨터를 카운트하면서 진행하면 된다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int v, e;
vector<int> computer[101];
bool vis[101];

int bfs()
{
	int cnt = 0;
	queue<int> q;
	q.push(1);
	vis[1] = true;
	while (!q.empty())
	{
		int now = q.front();
		q.pop();

		for (int i = 0; i < computer[now].size(); ++i)
		{
			int next = computer[now][i];
			if (!vis[next])
			{
				cnt++;
				vis[next] = true;
				q.push(next);
			}
		}
	}

	return cnt;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> v >> e;
	for (int i = 0; i < e; ++i)
	{
		int a, b;
		cin >> a >> b;
		computer[a].push_back(b);
		computer[b].push_back(a);
	}

	cout << bfs() << '\n';
	return 0;
}