유니온 파인드
Union 연산 - 두 그룹을 합치는 연산
Find 연산 - 원소가 속해 있는 그룹(또는 정점의 루트 부모)을 알아내는 연산
*두 그룹을 합치는 과정에서 그룹(또는 정점의 루트 부모)을 찾아야하기 때문에 union 함수 내부에 find 함수가 들어가야 한다.
방식 1 - 그룹 번호(값)을 변경하는 경우
원소별로 그룹의 번호를 배열로 가짐(초기값은 자신의 번호, 1부터 시작)
(정점 B를 정점 A와 연결하고자 할때)
=> 정점 B를 포함하여 B와 동일한 값(= 같은 그룹 번호를 가지는)을 가지는 원소들을 모두 그룹 A의 값으로 바꿔줘야 함
예제)
[1, 2, 3, 4, 5] 가 있을 때, 정점 3이 정점 2와 합쳐지는 경우 [1, 2, 2, 4, 5] 가 된다. 이는 정점 3이 정점 2가 속한 그룹 번호를 가짐으로서 같은 그룹임을 표시한 것이다.
[1, 2, 2, 4, 5] 에서 정점 3을 정점 1과 합치는 경우 아래와 [1, 1, 1, 4, 5] 가 된다. 이 과정에서 정점 3을 포함한 같은 그룹의 값들을 모두 정점 1의 그룹 번호인 1로 변경해주게 된다
[1, 1, 1, 4, 5] 에서 정점 3을 정점 4와 합치는 경우 [1, 1, 1, 1, 5] 가 된다. 정점 4의 그룹을 정점 3의 그룹값으로 바꾸는 과정이 진행되었다.
방식 2 - 트리 구조를 기대하며 대상 정점만을 연결하는 경우
사용할 수 없는 이유, 구조가 깨짐
예를 들어 [1, 2, 3, 4, 5]에서 정점 3을 정점 2에 합치면 [1, 2, 2, 4, 5]가 되고, 여기서 정점 3을 정점 1에 합치게 되면 [1, 2, 1, 3, 4]가 되는데, 이렇게 되면 정점 3이 정점 2와 연결된다는 정보가 사라지게 된다. 따라서 트리 구조를 사용하려면 방식 3, 4를 사용해야 한다.
방식 3 (트리구조) - 가장 상위 부모를 연결하는 경우
각 원소는 자신과 연결된 트리 기반의 정점(가장 상위 부모)의 인덱스를 값으로 가짐(초기값은 자신의 번호, 1부터 시작)
=> 이 방식의 경우 트리 구조를 사용한다. *parent 배열은 해당 인덱스의 정점이 연결된 트리의 루트 노드의 인덱스를 저장한다.
=> 정점 B를 정점 A와 연결하고자 할때, 정점 B와 트리를 위로 올라가면서 가장 상위 노드(루트 부모)를 정점 A와 연결시키면 됨
=> 정점 B와 연결된(같은 그룹인) 원소들을 모두 이동시키지 않으면서 트리구조를 통해 부모-자식 관계로 관리함으로서 그룹화를 지을 수 있다.
예제)
[1, 2, 3, 4, 5] 일때, 정점 3과 정점 2가 합쳐지는 경우 3의 가장 상위 부모(현재는 자신)을 정점 2를 가리키도록 한다. 따라서 [1, 2, 2, 4, 5] 가 된다.
[1, 2, 2, 4, 5]에서 정점 3이 정점 1과 합쳐지는 경우 정점 3의 가장 상위 부모(현재 2)가 정점 1을 가리키도록 한다. 따라서 [1, 1, 2, 4, 5] 가 된다.
[1, 1, 2, 4, 5] 에서 정점 4가 정점 3과 합치게 되는 경우 정점 3의 루트 부모가 1이므로 정점 4가 정점 1을 가리키게 된다.[1, 1, 2, 1, 5] 가 된다.
경로 압축이 없는 findP 함수
int findP(int x){
if(parent[x] != x)
{
return parent[x];
}
return findP(parent[x]);
} 방식 4 (트리구조) - 정점 B의 모든 상위노드를 정점 A와 연결(방식 3의 업그레이드)
find 함수에서 노드 x의 부모 노드를 찾는 과정에서 가장 상위 부모를 찾아서 트리를 내려오면서, 거치는 노드들의 부모를 루트 노드로 모두 교체한다. 이를 경로 압축이라 한다.
주의 사항
경로 압축이 반복 일어나면 트리가 점차 납작해지는거지 경로 압축이 일어났다고 해서 모든 정점이 높이가 1이 되는 것을 보장하는게 아니다. 즉 임의의 노드들은 여전히 루트가 아닌 중간 노드를 부모로 가지는 경우가 존재할 수 있다.
예제)
[1,2,3,4,5] 에서 정점 3과 2가 합쳐지는 경우 [1,2,2,4,5] 가 된다.
[1,2,2,4,5] 에서 정점 3을 정점 1과 합치는 경우 [1,1,2,4,5] 가 된다.
[1,2,2,4,5] 에서 정점 4를 정점 3에 합치는 경우 정점 4의 루트 부모는 4, 정점 3의 루트 부모는 1인데, 루트 부모를 찾는 과정에서 경로 압축이 일어나 [1,1,1,4,5]이 된다. 이후 정점 4(정점 4의 루트 부모)가 정점 1을 가리키도록 하면[1,1,1,1,5] 가 된다.
경로 압축이 존재하는 findP 함수
int findP(int x){
if(parent[x] != x) {
return parent[x] = findP(parent[x]);
}
return parent[x];
} 코드 (Java)
첫 줄에 N(정점의 수), M(간선 정보 수) 이 주어지고, 그 다음 M 개의 줄에 정점 간 간선 정보 수가 주어질 때, 생길 수 있는 그룹의 개수를 반환하는 기본 예제
public class Main {
static int[] parent; // 트리의 루트
// n1에 n2를 합친다고 가정(조건에 따라 달라지겠지만)
static void union(int n1, int n2) {
int p1 = findP(n1);
int p2 = findP(n2);
if(p1 < p2){
parent[p2] = p1;
}
else if(p2 < p1){
parent[p1] = p2;
}
}
// 경로 압축을 진행하며 루트 노드를 찾음
static int findP(int n) {
if (parent[n] != n) return parent[n] = findP(parent[n]);
return parent[n];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
parent = new int[N+1];
for(int i = 1; i <= N; i++) parent[i] = i;
for(int i = 0; i < M; i++){
st = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
if(findP(n1) == findP(n2)){
continue;
}
union(n1,n2);
}
Set<Integer> s = new HashSet<>();
for(int i = 1; i <= N; i++){
s.add(findP(i));
}
System.out.print(s.size());
}
}주의 사항!!!
앞서 언급했든 경로 압축이 일어났다고 해서 모든 정점의 높이가 1(부모 노드가 1개)임을 보장하지는 않는다. 때문에 그룹의 개수를 구하기 위해서는 parent 배열의 각 인덱스(정점 번호) 각각에 대해 findP 를 한번씩 돌려줘야 모든 트리의 높이가 1이 된다.
Set<Integer> s = new HashSet<>();
for(int i = 1; i <= N; i++){
s.add(findP(i));
}
System.out.print(s.size());