❓문제 설명

문제 : 백준 2606 바이러스
난이도 : 실버 3

문제 요약

• 한 컴퓨터가 바이러스가 걸리면 연결되어있는 모든 컴퓨터들이 바이러스에 감염되게 됩니다.
• 1번 컴퓨터가 바이러스에 걸리게 됐을 때 주어진 컴퓨터들의 연결상태에 따라 얼마나 많은 컴퓨터가 감염되었는지 출력하면 되는 문제 입니다.

🎯문제 해결 방법

문제를 읽고 DFS/BFS 문제임을 알았다면 정말 쉬운 문제였습니다.

한 컴퓨터를 시작으로 다른 컴퓨터들을 한번의 DFS 또는 BFS 알고리즘을 이용하여 감염시킬 수 있는지 구하면 됩니다.

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

컴퓨터 둘의 연결 정보는 방향이 없는 그래프로써 양방향으로 정보를 입력받습니다.

dfs(1)
1번 컴퓨터를 시작으로 DFS를 한번 도는 것을 이용하여 문제를 풀었습니다.

void dfs(int k) {
	if(k > n) return;
	vst[k] = 1;
	for(auto e : v[k]){
		if(!vst[e]){
			ret++; //몇대의 컴퓨터가 재귀적으로 감염되는지 확인합니다.
			dfs(e);
		}
	}
	return;
}

💻전체 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int ret;
int n,m;
vector<int> v[104];
bool vst[104];

void dfs(int k) {
	if(k > n) return;
	vst[k] = 1;
	for(auto e : v[k]){
		if(!vst[e]){
			ret++;
			dfs(e);
		}
	}
	return;
}

int main(void){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	cin >> m;
	for(int i=0; i<m; i++){
		int a,b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1);
	cout << ret;
	return 0;
}