유니온 파인드(Union Find)알고리즘이란 무엇인가?(+ 백준 1717번 : 집합의 표현)
코딩테스트 알고리즘 유형을 보던중 유니온 파인드라는 유형을 보게 되었고, 무엇인지 궁금해서 정리하면서 공부해보려고 한다.
유니온 파인드(Union Find)란?
유니온 파인드(UnionFind)란 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘으로 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어져있다.
서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다.
위의 그래프에서 3번과 7번이 연결되어 있는지 확인하기 위해서는 DFS/BFS를 통해서 찾을 수 있지만, 이 외에 다른 노드들의 정보(예를 들어 5번과 9번 노드가 연결되었는지, 2번과 6번 노드가 연결 되었는지)를 확인하고 싶을 수 있다. 이 외에도 현재는 적은 노드수의 그래프이지만, 노드수가 많아지게 되면 연결 여부를 확인하는대 오래걸리게 될 것이다.
만약 노드들 사이의 관계 정보가 중요한 것이 아닌 연결 여부가 중요하다면,
매번 연결 여부를 확인하기 위해 부모 노드를 찾아가는 작업 대신, 아래 그림과 같이 그래프를 바꿀 수 있다.
3번과 7번이 연결되었는지 확인하기 위해서는 부모의 노드가 같은지만 확인하면 되는 것이다.
유니온/파인드 알고리즘
유니온 파인드 알고리즘은 유니온 함수와 파인드 함수가 연결되어 있는 것과 같다.
파인드(Find) : 재귀적으로 부모를 찾으면서 가장 상위의 루트노드가 무엇인지 찾는다.
7번의 루트노드를 찾기위해 부모의 부모 노드를 찾다보면, 루트노드는 1임을 확인할 수 있다.
유니온(Union) : 두개의 서로 다른 노드의 부모가 같다면 두 노드를 합쳐준다.(노드간의 관계는 사라진다.)
7번의 루트노드를 찾기 위해 만났던 6번 노드와 5번 노드들의 루트 노드 또한 1번임으로 1번 노드와 직접적으로 연결해준다.
예제 문제
https://www.acmicpc.net/problem/1717
1717번: 집합의 표현
초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작
www.acmicpc.net
문제
초기에 N+1개의 집합 {0},{1},{2},…,{N}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
입력
첫째 줄에 N,M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. 다음 M개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b 의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b 의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다.
출력
1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
public class Main {
static int[] parent;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
parent = new int[N+1];
//parent배열 초기화
for(int i=1; i<=N; i++) {
parent[i] = i;
}
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine()," ");
int command = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if(command == 0) {
union(a,b);
}
else {
sb.append(isSameParent(a,b)? "YES\n" : "NO\n");
}
}
System.out.println(sb);
}//end Main
//a와 b를 연결 시킬 union함수
private static void union(int a, int b) {
//a와 b의 부모를 찾는다.
a = find(a);
b= find(b);
//만약 a와 b의 부모가 다르다면, b의 부모를 a로 연결 / 부모가 같다면 넘어감
if(a!=b) {
if(a<b) {
parent[b] = a;
} else {
parent[a] = b;
}
}
}//end union
//a와 b의 루트노드를 찾는 find함수
private static int find(int a) {
//a의 부모가 자기자신이라면 루트노드 이므로 리턴 a
if(parent[a] == a) {
return a;
}
//그게 아니라면, 재귀호출로 parent[a]의 부모를 확인
return parent[a] = find(parent[a]);
}//end find
//a와 b가 같은 부모를 같는지 확인하는 isSameParent함수
private static boolean isSameParent(int a, int b) {
a = find(a);
b = find(b);
if(a==b) {
return true;
}
return false;
}//end boolean
}
참고자료