백준 2606번: 바이러스

백준 온라인 저지(BOJ) 2606번 문제

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

1. 문제 요약

컴퓨터 간 연결 정보들이 주어질 때,

1번 컴퓨터를 통해 바이러스에 감염되는 컴퓨터의 수를 구하기

2. 알고리즘

간단한 형태의 탐색 문제이다.

마지막에 합을 더해줄 때 1번 컴퓨터는 제외하고 더해줘야 한다는 점에 주의.

여러 효율적인 방법이 있겠지만... 역시 속도가 생명..

3. 코드

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

using namespace std;

int main() {
	vector<int> connect[100];
	int inf[100] = { 0 };
	
	int N, M;

	scanf("%d %d", &N, &M);
	int t1, t2;
	for (int i = 0; i < M; ++i) {
		scanf("%d %d", &t1, &t2);
		connect[--t1].push_back(--t2);
		connect[t2].push_back(t1);
	}

	
	inf[0] = 1;
	queue<int> q;
	q.push(0);
	int u;
	while (q.empty() == false) {
		u = q.front();
		q.pop();
		for (int i = 0; i < connect[u].size(); ++i) {
			if (inf[connect[u][i]] == 0) {
				inf[connect[u][i]] = 1;
				q.push(connect[u][i]);
			}
		}
	}

	int count = 0;
	for (int i = 1; i < N; ++i) count += inf[i];
	
	printf("%d\n", count);

	return 0;
}