백준 2806 바이러스

 

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

 

서론

 

그래프와 BFS에 대한 이해가 필요하다.

 

아이디어

 

1. vector로 그래프를 만든다.

2. 1번 컴퓨터를 큐에 넣는다.

3. 큐에서 컴퓨터 하나를 가져오고, 가져온 컴퓨터와 연결된 컴퓨터들 중 방문하지 않은 컴퓨터들을 방문처리하고 큐에 넣는다. 방문처리할때 감염된 컴퓨터 개수를 +1시킨다.

4. 큐가 비어있을 때까지 3번을 반복한다.

5. 감염된 컴퓨터 개수를 출력한다.

 

구현

 

vector 개수를 100으로 만들면 런타임에러가 발생한다.

100번 컴퓨터를 참조하기 위해서는 0~100까지 101개를 만들어줘야한다.

 

// c++

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

using namespace std;
queue<int>q;
vector<int>v[101];
int computer[100];
int result;

void input() {
	int node, edge;
	cin >> node >> edge;
	for (int i = 0; i < edge; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
}

void bfs(int com) {
	q.push(com);
	computer[com] = 1;
	while (!q.empty()) {
		int c = q.front();
		int vSize = v[c].size();
		q.pop();
		for (int i = 0; i < vSize; i++) {
			if (computer[v[c][i]] == 0) {
				q.push(v[c][i]);
				computer[v[c][i]] = 1;
				//cout << v[c][i] << endl;
				result++;
			}
		}

	}
}

int main() {
	input();
	bfs(1);
	cout << result;
}