[2606] 바이러스, C++

한줄 후기 : 무서운 바이러스 

 

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

2606번: 바이러스

1번 컴퓨터를 통해 걸린 바이러스 이므로 DFS나 BFS로 1번부터 돌면서 cnt++ 하면된다. 

주의 할 점은 1번 컴퓨터는 제외 이니 마지막에 cnt-1 해줘야함.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
bool visit[101]={false}; 
vector<int> met[101];
int dfs(int start);
int cnt=0;
int main(){
	int n, m;
	cin >> n >> m;
	for(int i=1; i<=m; i++){
		int u, ver;
		cin >> u >> ver;
		met[u].push_back(ver);
		met[ver].push_back(u);
	}
	for(int i=1; i<=n; i++){
		sort(met[i].begin(), met[i].end());
	} 
	dfs(1);
	cout << (cnt-1);
}
int dfs(int start){
	cnt++;
	visit[start] = true;
	for(int i=0; i < met[start].size(); i++ ){
		int next = met[start][i];
		if(visit[next]==false)	dfs(next);
	}
}

DFS 이용 코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
bool visit[101]={false}; 
vector<int> met[101];
int bfs(int start);
int cnt=0;
int main(){
	int n, m;
	cin >> n >> m;
	for(int i=1; i<=m; i++){
		int u, ver;
		cin >> u >> ver;
		met[u].push_back(ver);
		met[ver].push_back(u);
	}
	for(int i=1; i<=n; i++){
		sort(met[i].begin(), met[i].end());
	} 
	bfs(1);
	cout << (cnt-1);
}
int bfs(int start){
	queue<int> q;
	visit[start] = true;
	q.push(start);
	while(!q.empty()){
		int now = q.front();
		q.pop();
		cnt++;
		for(int i=0; i<met[now].size(); i++){
			int next = met[now][i];
			if(visit[next]==false) {
				visit[next] = true;
				q.push(next);
			}
		} 
	}
}

BFS 이용 코드