[BOJ_2606][BFS]바이러스

네트워크에 연결된 컴퓨터 중, 1번 컴퓨터로 인해 바이러스가 전파된 컴퓨터의 수를 구하는 문제입니다. 유의할 점은 데이터를 받으며 그래프 정보를 입력 시 양방향으로 입력해주는 것과, Queue에 Push할 때 방문처리를 해주는 것입니다.

 

1. 그래프 입력 

2. 시작 노드 Push 후 방문처리 

3. BFS : 2차원 배열 BFS와는 다르게 갈 수 있는 방향이 그래프에 연결되 노드의 개수만큼 있습니다. 방문 후 Push 될 경우 감염된 컴퓨터의 수를 증가시키며, 1번 컴퓨터는 세지 않기 때문에 0부터 시작합니다.  

---

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std; 

queue<int> q;
vector<int> com[105];
int vis[105];

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);
	//freopen("input.txt", "r", stdin);
	
	// n = number of computers
	// m = number of connections
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		com[a].push_back(b);
		com[b].push_back(a);
	}	
	q.push(1);
	vis[1] = 1;
	int infected = 0;
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (int dir = 0; dir < com[cur].size(); dir++) {
			int nx = com[cur][dir];
			if (vis[nx]) continue;
			q.push(nx);
			vis[nx] = 1;
			infected++;
		}
	}
	cout << infected << '\n';
	return 0;
}