백준 2606번: 바이러스

 

 

 

DFS, BFS, Union-Find를 사용하여 풀수 있는 문제다.

 

 

1. DFS(재귀)

#include <iostream>
#include <queue>
#include <cstring> //memset
using namespace std;

const int MAX = 100 + 1;

int N, M;
int adjacent[MAX][MAX];	// 1이면 연결됨을 의미
bool visited[MAX];
int cnt;

// DFS 재귀
void DFS(int v) {
	
	cnt++;
	for (int i = 1; i <= N; i++) {
		// 연결되어있고 방문하지 않은 노드일 때
		if (adjacent[v][i] && !visited[i]) {
			visited[i] = 1;
			DFS(i);
		}
	}
}


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int from, to;
		cin >> from >> to;
		adjacent[from][to] = 1;
		adjacent[to][from] = 1;
	}

	visited[1] = 1;
	DFS(1);
	cout << cnt-1 << endl;
	
	
	return 0;
}

 

 

 

2. BFS

#include <iostream>
#include <queue>
#include <cstring> //memset
using namespace std;

const int MAX = 100 + 1;

int N, M;
int adjacent[MAX][MAX];	// 1이면 연결됨을 의미
bool visited[MAX];
queue<int> q;
int cnt;

// BFS 큐
void BFS(int v)
{
	q.push(v);

	// 시작노드와 가까운 노드부터 차례대로 큐에 넣어짐
	while (!q.empty()) {
		cnt++;

		v = q.front(); // 부모노드로 재정의
		q.pop();

		// 해당 노드에 인접한 노드들을 모두 큐에 넣음
		for (int i = 1; i <= N; i++) {
			if (adjacent[v][i] && !visited[i]) {
				visited[i] = 1;
				q.push(i);
			}
		}
	}
	
}


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int from, to;
		cin >> from >> to;
		adjacent[from][to] = 1;
		adjacent[to][from] = 1;
	}

	visited[1] = 1;
	BFS(1);
	cout << cnt-1 << endl;
	
	
	return 0;
}

 

 

3. Union-Find

#include <iostream>
#include <algorithm>
#include <cstring> //memset
using namespace std;

const int MAX = 100 + 1;

int N, M;
int arr[MAX];

int findParent(int num) {
	if (arr[num] < 0)
		return num;
	int parent = findParent(arr[num]);
	arr[num] = parent;
	return parent;
}

void merge(int aParent, int bParent) {

	//집합의 크기가 큰 쪽으로 합쳐짐
	if (abs(arr[aParent]) >= abs(arr[bParent])) {
		arr[aParent] += arr[bParent];
		arr[bParent] = aParent;
	}
	else {
		arr[bParent] += arr[aParent];
		arr[aParent] = bParent;
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	cin >> N >> M;

	memset(arr, -1, sizeof(arr));

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;

		if (a == b)
			continue;

		int aParent = findParent(a);
		int bParent = findParent(b);

		if (aParent == bParent)
			continue;

		merge(aParent, bParent);
	}
	
	// 노드 1이 속한 트리의 root를 찾음
	int cnt = findParent(1);

	// 노드 1이 속한 트리 root의 arr값의 절댓값은 트리의 크기
	// 노드 1은 제외이므로 -1해줌
	cout << abs(arr[cnt]) - 1 << endl;

	return 0;
}