[Silver 3] 2606번 바이러스

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

2606번: 바이러스

 

이 문제는 BFS를 사용해서 해결할 수 있다.

 

웜 바이러스는 양방향 그래프의 특성을 가진다. 

또한 웜 바이러스가 감염 시킬 수 있는 컴퓨터의 최대 수는 N이다.

 

이러한 점을 통해 반복문으로 통해 N까지 순회하고 현재 컴퓨터에서 웜이 뻗어 나갈 수 있는 컴퓨터를 찾는다.

감염시킬 컴퓨터가 있다면 counter를 증가시킨다.

 

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

char graph[101][101] = { 0, };
int visited[101]= { 0, };
int N, M, counter = 0;
queue<int> q;

void bfs() {
	q.push(1);
	visited[1] = 1;

	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i <= N; i++) {
			if (!graph[now][i]) continue;
			if (!visited[i]) {
				q.push(i);
				visited[i] = 1;
				counter += 1;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;
	cin >> M;

	for (int i = 0; i < M; i++) {
		int go, to;
		cin >> go >> to;
		graph[go][to] = 1;
		graph[to][go] = 1;
	}
	bfs();
	cout << counter << '\n';
}