[BOJ 2606] 바이러스

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

2606번: 바이러스

---

 

위 문제는 간단하게 BFS로 풀 수 있다.

 

1번 컴퓨터에서 갈 수 있는 모든 컴퓨터를 구하면, 몇 개의 컴퓨터가 바이러스에 걸리는지 알 수 있다.

 

이를 위해서

1. 큐에 1번을 넣음
2. 큐에서 값을 하나 꺼냄
3. 꺼낸 값과 연결된 모든 값 중 방문하지 않은 곳을 큐에 넣음
4. 큐에 넣을 때마다 바이러스가 걸린 컴퓨터 개수를 추가함
5. 큐가 빌 때까지 2 ~ 4를 반복함

---

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

int n, m;

vector<vector<int>> v;
int a[101];

int main()
{
	scanf("%d%d", &n, &m);
	v.resize(n + 1);
	for(int i = 0; i < m ;i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	queue<int> q;
	q.push(1);
	a[1] = 1;

	int cnt = 0;
	while (!q.empty())
	{
		int p = q.front(); q.pop();

		for (auto s = v[p].begin(); s != v[p].end(); s++)
		{
			if (!a[*s])
			{
				a[*s] = 1;
				q.push(*s);
				cnt++;
			}
		}
	}
	printf("%d", cnt);
}