유니온 파인드 (union-find)
유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.
일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다.
https://ip99202.github.io/posts/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C(Union-Find)/
유니온 파인드(Union-Find)
유니온 파인드란? 유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다. 노드를 합치는 Unio
ip99202.github.io
(이론 관련 좋은 글)
유니온 파인드의 핵심 이론
유니온 파인드는 union, find 연산을 완벽히 이해하는 것이 핵심이다. 두 연산은 다음과 같다. 이 설명을 염두에 두고 원리를 공부해 보자.
union, find 연산
- union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산. 노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b)는 A ∪ B를 말한다.
- find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산. 노드 a가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환한다.
유니온 파인드의 원리 이해하기
두 연산을 알아봤으므로 이번에는 유니온 파인드 알고리즘 구현 방법을 설명하겠다.
1. 유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것이다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다. 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스값으로 초기화한다.
2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행한다. 배열을 보면 1, 4와 5, 6을 union 연산으로 연결한다. 배열[4]는 1로, 배열[6]은 5로 업데이트한다(무조건 값이 작은 노드를 대표 노드로 설정한다고 했을 때). 1은 대표 노드, 4는 자식 노드로 union 연산을 하므로 배열[4]의 대표 노드를 1로 설정한 것이다. 다시 말해 자식 노드로 들어가는 노드값 4를 대표 노드값 1로 변경한 것이다. 그 결과 각각의 집합이었던 1, 4는 하나로 합쳐진다. 이는 그래프에서 연결해 준다는 뜻과 같다.
이제 union(4, 6)으로 4와 6을 연결해 보자. 그런데 4, 6은 대표 노드가 아니다. 그래서 각 노드의 대표 노드를 찾아 올라간 다음 그 대표 노드를 연결한다. 지금의 경우 4의 대표 노드 1에 6의 대표 노드 5를 연결한 것이다. 배열은 그럼 [1, 2, 3, 1, 1, 5]가 된다. 배열 상태로 보면 그래프의 연결이 잘 안 보일 수도 있겠지만 다음 find 연산 설명을 보면 위 배열이 그래프 연결을 잘 나타내고 있다는 것을 쉽게 이해할 수 있을 것이다.
3. find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산이다. find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 향상시킨다.
find 연산의 작동 원리
1. 대상 노드 배열에 index 값과 value 값이 동일한지 확인한다.
2. 동일하지 않으면 value 값이 가리키는 index 위치로 이동한다.
3. 이동 위치의 index 값과 value 값이 같을 때까지 1~2를 반복한다. 반복이므로 이 부분은 재귀 함수로 구현한다.
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드값으로 변경한다.
find 연산은 잘 생각하면 시간 복잡도가 줄어드는 효과를 얻게 된다. 연산을 할 때 거치는 노드들이 대표 노드와 바로 연결되는 형태로 변경되는 것을 알 수 있다. 이렇게 되면 추후 노드와 관련된 find 연산 속도가 O(1)로 변경된다.
위의 예를 보면 한 번의 find 연산을 이용해 모든 노드가 루트 노드에 직접 연결되는 형태로 변경되는 것을 볼 수 있다. 이러한 형태로 변경되면 이후 find 연산이 진행될 때 경로 압축의 효과가 나타난다. 예를 들어 이후 find(4) 연산을 수행하면 한 번의 이동으로 바로 대표 노드를 찾을 수 있게 된다.
(경로 압축은 실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형해 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법을 말한다.)
(실제로 여기서는 어떤 경로로 연결되어 있는지는 관심이 없고, 두 노드가 하나의 집합에 속하는지, 즉 연결되어 있는지 확인하는 것이 목적이다. 그렇기에 그래프의 형태를 바꿔주어도 훨씬 더 빠른 시간 내에 찾을 수 있으므로 문제가 없다. 재귀 함수를 빠져나오며 value의 값들을 루트 값으로 바꿔주는 것을 잊지 말자.)
[백준 1717번] 집합의 표현
https://www.acmicpc.net/problem/1717
최대 원소의 개수 1,000,000과 질의 개수 100,000이 큰 편이므로 경로 압축이 필요한 전형적인 유니온 파인드 문제이다.
1. 처음에는 노드가 연결돼 있지 않으므로 각 노드의 대표 노드는 자기 자신이다. 각 노드의 값을 자기 인덱스값으로 초기화한다.
2. find 연산으로 특정 노드의 대표 노드를 찾고, union 연산으로 2개의 노드를 이용해 각 대표 노드를 찾아 연결한다. 그리고 질의한 값에 따라 결과를 반환한다.
find 연산을 수행할 때 재귀 함수에서 나오면서 탐색한 모든 노드의 대표 노드값을 이번 연산에서 발견한 대표 노드로 변경하는 부분과, union 연산에서 선택된 노드끼리 연결하는 것이 아닌 선택된 노드의 대표 노드끼리 연결하는 부분이 유니온 파인드에서 가장 많이 실수하는 부분이다.
실제로 나는 union 부분에서 그냥 A[b]에 find(a)를 한 값을 넣으면 되겠지 했다가 틀렸다. 위의 사진에서 union(3, 7)을 할 때, 그냥 A[7] = find(3)을 해버리면 인덱스 7의 자리에 3의 루트 값인 1이 들어가게 된다. 그렇게 되면 6과 7의 연결이 끊어지게 되므로 반드시 항상 대표 노드끼리 연결을 해줘야 한다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
static int[] parent;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
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 = 0; 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 { // 같은 집합의 원소인지 확인하기
if (find(a) == find(b)) {
bw.append("YES\n");
} else {
bw.append("NO\n");
}
}
}
bw.flush();
bw.close();
}
private static void union(int a, int b) {
// !! 대표 노드끼리 연결 !!
a = find(a);
b = find(b);
if (a != b) {
parent[a] = b;
}
}
private static int find(int a) {
if (parent[a] == a)
return a;
else
return parent[a] = find(parent[a]);
/*
중요!! parent[a]에 넣어줘야 경로 압축이 됨.
배열에 들어있는 a의 value 값을 계속 따라가며 재귀를 호출하다가,
대표 노드를 만났을 때 다시 돌아오면서 반환받은 그 값을 계속 넣어주기.
(parent[a] 부분은 재귀를 호출하기 전 a 값이므로 변경되지 않음.
예)
index : 1 2 3 4 5
value : 1 1 2 3 4
일 때, find(5)를 한다면
find(5) -> find(4) -> find(3) -> find(2) -> find(1) => 1
1은 index와 같으므로 현재의 부모 노드로 판단, 재귀를 빠져나옴.
find(2)에 1을 리턴 -> find(3)에 1을 리턴 -> find(4)에 1을 리턴 -> find(5)에 1을 리턴
각각 리턴하며 1을 value로 저장
결국 find(5)를 한 후 배열의 값은 모든 노드가 1을 부모로 다이렉트로 바라보는 형태가 됨 (<- 경로 압축)
1 2 3 4 5
1 1 1 1 1
*/
}
}
재귀 함수 부분을 잘 보자.
[백준 1976번] 여행 가자
https://www.acmicpc.net/problem/1976
도시의 연결 유무를 유니온 파인드 연산을 이용해 해결할 수 있다는 아이디어를 떠올릴 수 있으면 쉽게 해결할 수 있는 문제이다 (이게 제일 어려운 것 같다). 일반적으로 유니온 파인드는 그래프 영역에서 많이 활용되지만, 위 문제와 같이 단독으로도 활용할 수 있다는 점도 참고하라. 이 문제에서는 도시 간 연결 데이터를 인접 행렬의 형태로 주었기 때문에 인접 행렬을 탐색하면서 연결될 때마다 union 연산을 수행하는 방식으로 문제에 접근하면 된다.
1. 도시와 여행 경로 데이터를 저장하고, 각 노드와 관련된 대표 노드 배열의 값을 초기화한다.
2. 도시 연결 정보가 저장된 인접 행렬을 탐색하면서 도시가 연결돼 있을 때 union 연산을 수행한다.
3. 여행 경로에 포함된 도시의 대표 노드가 모두 같은지 확인한 후 결괏값을 출력한다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
static int[] parent;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
parent = new int[N+1];
for (int i = 0; i <= N; i++) // 대표 노드 자기 자신으로 초기화
parent[i] = i;
for (int i = 1; i <= N; i++) { // 도시 연결 데이터 받기
for (int j = 1; j <= N; j++) {
int ableToGo = sc.nextInt(); // 1 -> 연결, 0 -> 연결 X
if(ableToGo == 0) continue;
union(i, j);
}
}
sc.nextLine();
String str = sc.nextLine();
String[] route = str.split(" ");
// 여행 계획 도시들이 1개의 대표 도시로 연결돼 있는지 확인
int a = find(Integer.parseInt(route[0]));
for (int i = 1; i < M; i++) {
int b = find(Integer.parseInt(route[i]));
if (a != b) {
System.out.println("NO");
return;
}
}
System.out.println("YES");
}
static void union(int a, int b) { // 대표 노드끼리 연결
parent[find(a)] = parent[find(b)];
}
static int find(int a) {
if(parent[a] == a) return a;
else return parent[a] = find(parent[a]); // 재귀 함수 -> 경로 압축
}
}
[백준 1043번] 거짓말
https://www.acmicpc.net/problem/1043
(내 접근 방법)
거짓말 할 수 없는 경우는 다음과 같다.
1. 진실을 아는 사람이 있음.
2. 진실을 모르지만 나중에 진실을 아는 사람과 함께 또 오기 때문에 지금 거짓말 할 수 없음.
그러므로 진실을 아는 사람과 진실을 아는 사람과 함께 파티에 오는 사람들을 전부 한 그룹으로 (parent) 묶은 후 이 사람들이 안 올때를 count 하면 됨.
이 문제의 핵심은 파티에 참석한 사람들을 1개의 집합으로 생각하고, 각각의 파티마다 union 연산을 이용해 사람들을 연결하는 것이다. 이 작업을 하면 1개의 파티에 있는 모든 사람들은 같은 대표 노드를 바라보게 된다. 이후 각 파티의 대표 노드와 진실을 알고 있는 사람들의 각 대표 노드가 동일한지 find 연산을 이용해 확인함으로써 과장된 이야기를 할 수 있는지 판단할 수 있다.
1. (예제 입력 6) 진실을 아는 사람 데이터, 파티 데이터, 유니온 파인드를 위한 대표 노드 자료구조를 초기화한다.
2. union 연산을 수행해 각 파티에 참여한 사람들을 1개의 그룹으로 만든다.
3. find 연산을 수행해 각 파티의 대표 노드와 진실을 아는 사람들이 같은 그룹에 있는지 확인한다. 파티 사람 노드는 모두 연결돼 있으므로 아무 사람이나 지정해 find 연산을 수행하면 된다.
4. 모든 파티에 관해 과정 3을 반복해 수행하고, 모든 파티의 대표 노드가 진실을 아는 사람들과 다른 그룹에 있다면 결괏값을 증가시킨다.
5. 과장할 수 있는 파티의 개수를 결괏값으로 출력한다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
static int[] parent; // 대표 노드
static int[] trueP; // 진실 아는 사람들
static ArrayList<Integer>[] party; // 파티 정보
static int result;
public static void main(String[] args) throws IOException{
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int T = sc.nextInt();
result = 0;
trueP = new int[T];
for (int i = 0; i < T; i++) // 진실을 아는 사람 저장하기
trueP[i] = sc.nextInt();
party = new ArrayList[M];
for (int i = 0; i < M; i++) { // 파티 데이터 저장하기
party[i] = new ArrayList<>();
int party_size = sc.nextInt();
for (int j = 0; j < party_size; j++) {
party[i].add(sc.nextInt());
}
}
parent = new int[N + 1];
for (int i = 0; i <= N; i++) { // 대표 노드를 자기 자신으로 초기화하기
parent[i] = i;
}
for (int i = 0; i < M; i++) { // 각 파티에 참여한 사람들을 1개의 그룹으로 만들기
int firstPeople = party[i].get(0);
for (int j = 1; j < party[i].size(); j++) {
union(firstPeople, party[i].get(j));
}
}
// 각 파티의 대표 노드와 진실을 아는 사람들의 대표 노드가 같다면 과장할 수 없음
for (int i = 0; i < M; i++) {
boolean isPossible = true;
int cur = party[i].get(0); // 각 파티 사람 노드들은 다 연결되어 있으므로 아무나 상관 없음
for (int j = 0; j < trueP.length; j++) {
if (find(cur) == find(trueP[j])) {
isPossible = false;
break;
}
}
if (isPossible) result++; // 모두 다르면 결괏값 1 증가
}
System.out.println(result);
}
static void union(int a, int b) {
parent[find(b)] = parent[find(a)];
}
static int find(int a) {
if(parent[a] == a) return a;
else return parent[a] = find(parent[a]);
}
}
파티를 입력받으며 만약 파티를 가는 사람 중에 진실을 아는 사람이 있다면 거기 있는 전체 사람들을 해당 진실을 아는 사람과 하나로 엮으려고 했는데, 이렇게 하니 문제가 너무 복잡해졌다 (입력받을 때 진실을 아는 사람이 나중에 나올 수도 있음, 지금은 진실을 아는 사람과 같이 있지 않은데 미래에 같이 오게 될 수 있음 등등...). 위의 방법은 파티에 오는 사람들을 그냥 전부 하나로 묶어버리고, 나중에 진실을 아는 사람들을 하나씩 돌면서 파티 대표인과 (파티 같이 간 사람들은 전부 하나로 묶여있음, 같은 대표인임) 진실을 아는 사람들의 대표 노드가 같은지 하나씩 확인하는 훨씬 간단한 방법이다. 파티를 입력받을 때 살짝 꼬였는데, 그냥 ArrayList로 저장하면 간단해진다.
[참고자료]
- do it! 알고리즘 코딩 테스트 자바편
'알고리즘 > Do it! 알고리즘 코딩 테스트' 카테고리의 다른 글
| 다익스트라 (1) | 2024.06.15 |
|---|---|
| 위상 정렬 (1) | 2024.06.11 |
| 그래프의 표현 (1) | 2024.06.04 |
| 정수론 - 확장 유클리드 호제법 (0) | 2024.06.01 |
| 정수론 - 유클리드 호제법 (0) | 2024.05.31 |
