View
서로소 집합 자료구조 : union과 find 2개의 연산으로 구성
1) union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인
⑴ A와 B의 루트 노드 A', B'를 각각 찾는다.
⑵ A'를 B'의 부모 노드로 설정한다.
2) 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.
예를 들어, 전체 집합 {1, 2, 3, 4, 5, 6}이 6개의 원소로 구성되어 있는 상황을 생각해보자.
이때 다음과 같은 4개의 union 연산이 주어져 있다.
(union 1,4) (union 2,3) (union 2,4) (union 5,6)
이러한 union 연산들은 그래프 형태로 표현될 수도 있다. 각 원소는 그래프에서의 노드로 표현되고, '같은 집합에 속한다'는 정보를 담은 union 연산들은 간선으로 표현된다.
유의할 점은 실제 각 원소의 집합 정보를 표현하려면 트리 자료구조를 이용한다. 일반적으로 서로소 집합을 그림으로 표현할 때는 번호가 큰 노드가 번호가 작은 노드를 간선으로 가리키도록 트리 구조를 이용해 그림을 그리게 된다.
즉, 트리 구조상 번호가 작은 노드가 부모가 되고, 번호가 큰 노드가 자식이 된다.
이렇게 union 연산을 토대로 그래프를 그리면 '연결성'으로 손쉽게 집합의 형태를 확인할 수 있다.
union 연산을 하나씩 확인하면서 서로 다른 두 원소에 대해 합집합을 수행해야 할 때는, 각각 루트 노드를 찾아서 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 하면 된다.
📍 알고리즘 동작 과정
step0. 노드의 개수(V) 크기의 부모 테이블을 초기화한다. 이때 모든 원소가 자기 자신을 부모로 가지도록 설정한다.
현재 원소의 개수가 6이므로, 초기 단계에서는 총 6개의 트리가 존재하는 것과 같다.
여기에서 유의할 점은 부모 테이블은 말 그대로 부모에 대한 정보만을 담고 있다. 다시 말해 특정한 노드의 부모에 대해서만 저장하고 있다. 우리가 실제로 루트를 확인하고자 할 때는 재귀적으로 부모를 거슬러 올라가서 최종적인 루트 노드를 찾아야 한다.
step1. union 1,4
첫 번째 union 연산을 확인하면, 1과 4를 합친다. 이때는 노드 1과 노드 4의 루트 노드를 각각 찾으면 된다. 현재 루트 노드는 각각 1과 4이기 때문에 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정한다.
step2. union 2,3
step3. union 2,4
step4. union 5,6
📍 소스코드
package graph;
import java.util.*;
public class graph05 {
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
public static int v, e;
public static int[] parent = new int[100001]; // 부모 테이블 초기화하기
// 특정 원소가 속한 집합을 찾기
public static int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
// Union 연산을 각각 수행
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
unionParent(a, b);
}
// 각 원소가 속한 집합 출력하기
System.out.print("각 원소가 속한 집합: ");
for (int i = 1; i <= v; i++) {
System.out.print(findParent(i) + " ");
}
System.out.println();
// 부모 테이블 내용 출력하기
System.out.print("부모 테이블: ");
for (int i = 1; i <= v; i++) {
System.out.print(parent[i] + " ");
}
System.out.println();
}
}
모든 원소에 대하여 각 원소가 속한 집합 = 각 원소의 루트 노드로 이 루트 노드가 같은 원소끼리는 동일한 집합을 이룬다.
다만, 이렇게 구현하면 답을 구할 수는 있지만 find 함수가 비효율적으로 동작한다.
최악의 경우 find 함수가 모든 노드를 다 확인하는 터라 시간 복잡도가 O(V)가 됨. 결과적으로 현재의 알고리즘을 그대로 이용하게 되면 노드의 개수가 V개이고 find 혹은 Union 연산의 개수가 M개일 때, 전체 시간 복잡도는 O(VM)이 되어 비효율적임
-> 경로 압축 기법을 적용하여 find 함수 최적화 가능함
경로 압축은 find 함수를 재귀적으로 호출한 뒤에 부모 테이블값을 갱신하는 기법이다.
public static int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}이렇게 함수를 수정하면 각 노드에 대하여 find 함수를 호출한 이후에, 해당 노드의 루트 노드가 바로 부모 노드가 된다.
📚 실전문제
학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N + 1 개의 팀이 존재한다. 이때 선생님은 '팀 합치기'연산과 '같은 팀 여부 확인'연산을 사용할 수 있다.
1. '팀 합치기' 연산은 두 팀을 합치는 연산이다.
2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.
선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인'연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오.
📝 문제 해설
전형적인 서로소 집합 알고리즘 문제로 N과 M의 범위가 모두 최대 100,000이므로 경로 압축 방식의 서로소 집합 자료구조를 이용하여 시간 복잡도를 개선해야 함.
package graph;
import java.util.Scanner;
public class graph06 {
public static int n, m;
public static int[] parent = new int[100001];
public static int findParent(int x) {
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
for (int i = 0; i < m; i++) {
int oper = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
if(oper == 0){
unionParent(a, b);
}else if(oper == 1){
if(findParent(a) == findParent(b)){
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}
}
}
서로소 집합을 활용한 사이클 판별
무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.
간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하는 것만으로도 사이클을 판별할 수 있다.
1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
1) 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
2) 루트 노드가 서로 같다면 사이클이 발생한 것이다.
2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.
step0. 모든 노드에 대하여 자기 자신을 부모로 설정하는 형태로 부모 테이블을 초기화 한다.
step1. (1,2)를 확인한다. 더 큰 번호를 갖는 노드 2의 부모 노드를 1로 변경한다.
step2. (1,3)을 확인한다. 더 큰 번호를 갖는 노드 3의 부모 노드를 1로 변경한다.
step3. (2,3) 간선을 확인한다. 다만 이때 노드 2와 노드 3이 이미 루트 노드로 노드 1을 가지고 있다.
다시 말해서 사이클이 발생한다는 것을 알 수 있다.
이러한 사이클 판별 알고리즘은 그래프에 포함되어 있는 간선의 개수가 E개 일 때 모든 간선을 하나씩 확인하며,
매 간선에 대하여 union 및 find 함수를 호출하는 방식으로 동작한다.
이 알고리즘은 간선에 방향성이 없는 무향 그래프에서만 적용 가능하다.
import java.util.*;
public class graph06 {
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
public static int v, e;
public static int[] parent = new int[100001]; // 부모 테이블 초기화하기
// 특정 원소가 속한 집합을 찾기
public static int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
boolean cycle = false; // 사이클 발생 여부
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
// 사이클이 발생한 경우 종료
if (findParent(a) == findParent(b)) {
cycle = true;
break;
}
// 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
else {
unionParent(a, b);
}
}
if (cycle) {
System.out.println("사이클이 발생했습니다.");
}
else {
System.out.println("사이클이 발생하지 않았습니다.");
}
}
}'알고리즘 > 이코테' 카테고리의 다른 글
| 10. 그래프 이론 - 위상 정렬 (0) | 2022.07.25 |
|---|---|
| 09. 최단 경로 - 다익스트라 최단 경로 알고리즘 (0) | 2022.07.11 |
| [알고리즘] 08. 동적 계획법(Dynamic Programming) (0) | 2022.06.30 |