백준 BOJ 1717 - 집합의 표현

간단한 유니온파인드 문제

유니온파인드에 관해서는 여름학교 수업 끝나고 정리하면서 글을 하나 작성할 계획이다.

이걸 보시는 분들은 아마 내 블로그에 유니온파인드 관련 글이 있을거다.

​

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

1717번: 집합의 표현

유니온파인드는 간단히 말하자면

자신의 부모만을 기억하는 구조다

그래서 부모 노드가 자기 자신인 노드의 경우에는 자기자신이 하나의 루트노드가 되는 것이고,

두 집합끼리 합할 때에는 그냥 루트노드 하나가 다른 루트노드의 자식노드가 되게 설계해주면 된다.

#include <stdio.h>

int parent[1000010] = {0};

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

void union_f(int u, int v){
	int x = find(u);
	int y = find(v);
	if(x!=y) parent[x] = y;
	return;
}

int main(){
	int n,m,a,x,y;
	scanf("%d %d", &n, &m);
	
	for(int i=0; i<=n; i++) parent[i] = i;
	
	while(m--){
		scanf("%d %d %d", &a, &x, &y);
		if(!a) union_f(x,y);
		else{
			if(find(x)==find(y)) puts("YES");
			else	 			 puts("NO");
		}
	}
	return 0;
}

find(int k)가 자신이 포함된 트리의 루트노드를 찾는 함수이다.

자기자신이 부모인지를 확인해서, 자기자신이 부모이면 루트노드이므로 반환하고,

아닌경우에는 parent[k]에 루트노드의 값을 넣어주고 루트노드를 반환한다.

​

여기서 parent[k]에 루트노드의 값을 넣어주면

다음 find[k]의 과정이 더욱 더 빨라지기 때문에 이렇게 해주었다.

만약 parent[k]에 루트노드의 값을 넣어주지 않는다면

최대 시간복잡도는 O(N)에 해당한다.

​

union_f(int u, int v)는 두 트리를 합치는 소스코드이다

각자의 루트노드를 구한 다음

만약 둘의 루트노드가 같다면 이미 같은 트리상에 있으므로

굳이 합쳐줄필요가 없고

그렇지 않다면 하나의 트리가 다른 트리의 자식으로 들어간다.

​

두 원소가 같은 집합에 포함되어있는지 확인하는 방법은

하나의 트리는 반드시 루트노드를 단 하나 가지게 되므로

루트노드를 구해 비교했을때 같다면 같은 집합 내에 있는 것이다.

​

이렇게 잘 작성 해주면 무난하게 AC.

​

​