[백준] 2606 바이러스

문제출처] https://www.acmicpc.net/problem/2606

2606번: 바이러스

---

문제요약

1번 노드와 연결된 노드의 수 출력

풀이

그래프 탐색 알고리즘 (BFS 혹은 DFS) 을 이용하여 1번 노드와 연결된 노드들을 탐색하면 된다.

백준 1260번 DFS와 BFS 문제에서 구현한 알고리즘을 이용하면 문제를 해결할 수 있다.

2019/09/02 - [프로그래밍 공부/알고리즘] - [백준] 1260 DFS와 BFS

소스코드는 C/C++로 작성되었습니다.

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

using namespace std;

int infected_virus[101];
vector<int> network[101];

int search() {
	queue<int> q;
	int count = -1;
	infected_virus[1] = true;
	q.push(1);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		count++;
		for (int i = 0; i < network[x].size(); i++) {
			int y = network[x][i];
			if (!infected_virus[y]) {
				q.push(y);
				infected_virus[y] = true;
			}
		}
	}
	return count;
}


int main() {
	int computer_num, net_pair;
	cin >> computer_num >> net_pair;

	for (int i = 0; i < net_pair; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		network[v1].push_back(v2);
		network[v2].push_back(v1);
	}

	cout << search();

}