BOJ 2606 : 바이러스 (유니온 파인드 Union Find)

알고리즘 문제 전체 링크

 

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

 

 

유니온 파인드(Union Find)를 이용하면, 원소가 어떤 집합에 포함되어 있는지 알 수 있다.

 

유니온 파인드에서는 2가지 연산이 필요하다.

 

find(x) : x가 포함된 집합을 찾는다. (root 원소를 찾는다.)

makeUnion(x, y) : x와 y가 같은 집합에 포함되도록 합친다. parent[y] = x가 된다.

 

그리고 각 원소별로 자신의 부모를 저장할 parent 배열이 필요하다.

---

바이러스 문제는 그래프(링크드 리스트)를 만드는 기본 문제지만, 집합으로도 해결 가능하다.

 

이 문제에서는 1번 컴퓨터와 연결된 컴퓨터의 수를 찾아야 한다.

Find( 2 ~ N ) 과 Find( 1 )의 집합이 같으면 1번 컴퓨터와 연결되었다고 볼 수 있다.

 

먼저 예제에 대해 집합을 만들어보자. (1 2 / 2 3 / 1 5 / 5 2 / 5 6 / 4 7)

 

parent 배열은 i의 부모를 가르킨다. 처음에는 자기 자신을 가르키도록 한다.

int parent[MAX]; /* parent[i] : i의 parent */

 

입력 1 2 → makeUnion(1, 2), parent[2] = 1이 된다.

 

입력 2 3 → makeUnion(2, 3), parent[3] = 2이 된다.

 

parent[3]은 2이고, parent[2]는 1이기 때문에 결국 find(3)과 find(1)의 결과는 같다. (같은 집합이다.)

따라서 parent[3] = 1로 표시할 수 있다. 이 과정을 경로 압축이라고 한다.

 

입력 1 5 → makeUnion(1, 5), parent[5] = 1이 된다.

 

입력 5 2 → makeUnion(5, 2), parent[2] = 1, parent[5] = 1이므로 변화가 없다.

입력 5 6 → makeUnion(5, 6), parent[6] = 5, parent[5] = 1이므로 parent[6] = 1이 된다.

 

입력 4 7 → makeUnion(4, 7), parent[7] = 4가 된다.

 

parent[1, 2, 3, 5, 6] = 1이 되고, parent[4, 7] = 4가 되어 1과 연결된 컴퓨터는 총 4개가 된다.

---

구현

 

원소 1과 2가 같은 집합인지 확인하려면, find를 이용하여 1과 2의 root 부모의 원소가 같은지 확인하면 된다.

(find(1) == find(2))

 

find는 재귀 호출을 이용하여 아래와 같이 구현한다.

x == parent[x]면 자기 자신을 return하고, 그렇지 않으면 부모를 return한다. 

재귀 호출이므로 x == parent[x]인 경우까지 find가 계속 호출 되어 root 원소를 return한다.

int find(int x)
{
	if (x == parent[x]) return x;
	return find(parent[x]); 
}

 

만약 parent[N]의 부모가 N - 1, parent[N - 1] = N - 2, ... 최종적으로 parent[2] = 1이라고 하자.

N과 2가 같은 집합인지 확인하기 위해 N의 최종 부모를 찾기까지 O(N)이 걸린다.

 

따라서 find 함수에서 경로 압축을 적용하여 parent[N]이 최종적으로 1이 되도록 만든다.

int find(int x)
{
	if (x == parent[x]) return x;
	return parent[x] = find(parent[x]); // 경로 압축
}

즉, 실제 원소의 부모가 중요한 것이 아니라, 최종 root가 무엇인지가 중요하다.

 

find 함수를 만들었으니, makeUnion은 아래와 같이 만들 수 있다.

x와 y의 각 root 원소를 찾아서, parent 배열로 연결해준다.

/* y의 parent를 x로 설정 */
void makeUnion(int x, int y)
{
	x = find(x);
	y = find(y);

	if (x != y) parent[y] = x;
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (100 + 10)

int N, M;
int parent[MAX]; /* parent[i] : i의 parent */

int find(int x)
{
	if (x == parent[x]) return x;
	return parent[x] = find(parent[x]); // 경로 압축
}

void makeUnion(int x, int y)
{
	x = find(x);
	y = find(y);

	if (x != y) parent[y] = x;
}

int main(void)
{
	int ans;

	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++) parent[i] = i;

	for (int i = 0; i < M; i++)
	{
		int x, y;

		scanf("%d %d", &x, &y);
		makeUnion(x, y);
	}

	ans = 0;
	for (int i = 2; i <= N; i++)
		if (find(i) == find(1)) ans++;

	printf("%d\n", ans);

	return 0;
}