[백준 2606번 C++] 바이러스

DFS 혹은 BFS 를 사용하여 풀 수 있는 간단한 문제.

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

2606번: 바이러스

 

BFS 를 사용한 풀이 

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

const int MAX = 101;
int N, M;
int answer=0;
vector<int> network[MAX];
bool visited[MAX];
deque<int> Q;

int DFS(int v) {
	Q.push_back(v);
	visited[v] = true;

	while (!Q.empty()) {
		int cur = Q.front();

		Q.pop_front();

		for (int i = 0; i < network[cur].size(); i++) {
			if (!visited[network[cur][i]]) {
				Q.push_back(network[cur][i]);
				visited[network[cur][i]] = true;
				answer++;
			}
		}
	}

	return cnt;

}

int main() {
	cin >> N >> M;

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

	DFS(1);

	cout << answer << " ";
}

 

DFS를 사용한 풀이 

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

const int MAX = 101;
int N, M;
int answer = 0;
vector<int> network[MAX];
bool visited[MAX];
deque<int> Q;

void BFS(int v) {
	visited[v] = true;
	for (int i = 0; i < network[v].size() ; i++) {
		if (!visited[network[v][i]]) { 
			visited[network[v][i]] = true; 
			answer++;
			BFS(network[v][i]);
		}
	}
}

int main() {
	cin >> N >> M;

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

	BFS(1);

	cout << answer << " ";
}