[백준 #2606 c++] 바이러스, 전형적인 Union Find

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

2606번: 바이러스

 

그림을 보자마자 DFS보다 Union Find가 먼저 떠올랐다.

문제를 풀었을 때도 DFS가 아니라 Union Find가 정석이라고 생각했다.

이 문제는 Union Find를 응용한 크루스칼 알고리즘을 한 번이라도 풀어본 사람이라면 DFS나 BFS를 쓰지 않고 쉽게 풀 수 있는 문제다. 크루스칼에서는 정점을 탐색하면서 사이클을 이루는지 판별하기 위해 Union Find를 쓴다.

 

먼저 이 문제를 DFS로 풀 경우, 그래프의 탐색을 이용하여 visited 배열을 만든 후 이미 방문한 정점에 대해서는 카운트하지 않도록 한 후 새 정점을 방문할 때마다 카운트를 증가시키면 된다.

BFS의 경우 큐와 while문을 활용하여 인접 정점을 큐에 넣고 queue.empty() == false 를 조건문으로 넣어 탐색하면 된다.

 

반면 Union Find를 사용한다면 훨씬 코드가 간단해지고 각 정점이 속한 Union의 부모 정점을 표시할 수 있는 배열만 만들어 주면 된다.

 

#include <iostream>
using namespace std;

int parent[101];
int find(int child) { // union find
	if (parent[child] == child) return child;
	return parent[child] = find(parent[child]);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		int pa = find(a);
		int pb = find(b);

		if (pa < pb) {
			parent[pb] = pa;
		}
		else {
			parent[pa] = pb;
		}
	}
	int cnt = 0;
	for (int i = 2; i <= n; i++) {
		if (find(i) == 1) cnt++;
	}
	cout << cnt;
}

 

int find(int child) 함수는 child의 조상(바로 위 부모가 아니라 부모의 부모 형태로 추적하면서 최종 부모를 가리킴)을 찾는 함수이다. 새 정점을 방문할 때마다 부모가 바뀔 수 있다.

Union에서 부모를 택할 때 가장 큰 값과 작은 값 중 하나를 선택할 수 있지만 보통은 작은 값으로 하는게 일반적이다.

 

다음의 입력값을 보자.

 

6
5
1 2
3 4
4 6
5 4
6 2

 

1번부터 6번까지 총 6개의 컴퓨터가 존재하고 6 - 2가 연결되기 전까지의 그래프는 다음 그림과 같다.

현재 상태에서 1과 2의 부모는 1이고,

3, 4, 5, 6은 부모를 3으로 한다.

 

여기서 6 - 2를 연결하면

3을 부모로 하던 3, 4, 5, 6은 최종적으로 1을 부모로 하게 된다.

다같이 1을 부모로 하기 때문에 모두 1의 집합, 즉 Union에 속하게 된다.

 

따라서

parent[a] = pb가 아니라 parent[pa] = pb로 해주어야 한다.

자신의 부모만 바꾸는게 아니라 같은 부모를 섬기는 나머지 정점들에 대해서도 부모를 바꾸어주어야 하기 때문이다.

6 - 2를 새로 추가하기 전 상황에서는 parent[6] = 3, parent[2] = 1이다.

여기서 3의 부모를 1로 바꾸어주어야 하므로 parent[3] = parent[2] = 1 이 되는 것이다.

 

정점의 개수가 최대 100개이기 때문에 메모리에 대한 염려는 없지만 무지막지하게 크다면 vector를 사용하여 동적 배열을 만들면 된다.