[백준] 알고리즘 2606번 - 바이러스문제

문제

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

2606번: 바이러스

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v[100];
bool check[101];
int n, e, ans;
void dfs(int x) {
	ans++;
	check[x] = true;
	for (int i = 0; i < v[x].size(); i++) {
		int next = v[x][i];
		if (check[next]) continue;
		check[next] = true;
		dfs(next);
	}
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> e;
	for (int i = 0; i < e; i++) {
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1);
	cout << ans - 1;
}

해설

문제를 이해했다면, 1번컴퓨터로 시작했을 때 연결되어있는 부분들을 깊게 탐색해야 한다는 것을 바로 캐치하실 겁니다.

그렇다면 간단하게 dfs를 이용하여 문제를 해결할 수 있다.

메인부분에서는 인접정점들을 연결시켜주고 dfs를 1번컴퓨터부터 돌리게되면 감염된 바이러스 컴퓨터를 도출해낼 수 있다.