Union-Find에 대한 개념 설명부터 있습니다. 이미 알고 계신다면 아래 문제 부분부터 보시면 되겠습니다.
Union-Find는 자료구조 트리를 활용해 집합을 표현하는 자료구조이며 집합간의 합치거나(Union) 원소가 어느 집합에 포함되어 있는지를 찾는(Find) 연산이 매우 빠른 것이 특징입니다.
빠르게 찾는 다는 것은 최적화가 이루어졌을 때 대부분의 경우에서 상수 시간의 복잡도를 보이게 됩니다
Union-Find의 시작은 대부분 원소 한개로 이루어진 여러개의 집합으로 시작합니다.
이러한 집합을 1차원 배열에 저장해 주도록 하겠습니다. parent라는 배열을 만들고 자기 자신을 parent로 지정해주면 됩니다. 부모 노드를 의미하게 됩니다.
만약 1을 루트로 갖는 집합과 2를 루트로 갖는 집합을 합친다고 하면 둘 중 하나의 루트를 다른 루트의 자식으로 연결해주면 됩니다.(결국 이게 Union인데 아래에서 더욱 자세히 설명하도록 하겠습니다.) 합친 결과로 아래처럼 되겠네요.
자 그럼 이 상황에서 1과 2가 같은 집합에 들어있다는건 어떻게 알 수 있을까요?
아래처럼 어떤 원소를 입력받아 그 원소가 포함된 트리의 루트를 반환해주는 함수를 만들어주고 1과 2가 포함된 집합의 루트가 같다면 두 원소는 같은 집합에 포함되어 있다는 뜻이 됩니다. 그리고 이 루트를 반환해주는 함수가 바로 Union-Find의 Find가 됩니다.
static int find(int x, int[] parent){
return parent[x] == x? parent[x] : find(parent[x]);
}
if(find(1) == find(2))
System.out.print("1과 2는 같은 집합에 있다");
여기까지 해준다면 find의 시간 복잡도는 이 됩니다. 왜냐하면 아래와 같은 상황이 있을 수도 있기 때문입니다.
그러면 이 복잡도를 줄이기 위해서 어떤 방법이 있을까요?
바로 경로 압축이란 방법을 사용할 수 있습니다. 경로 압축의 아이디어는 바로 집합의 모든 노드의 부모를 루트 노드로 바꾸는 겁니다. 이걸 하기 위한 코드는 매우 간단합니다.
static int find(int x, int[] parent){
return parent[x] == x? parent[x] : (parent[x] = find(parent[x]);
}
위의 경로 압축 전 코드에서 parent[x] = find(parent[x])
만 수정해주었습니다. 결국 쭉쭉 타고 올라가면서 모든 노드의 parent를 루트 노드로 바꾸게 됩니다.
Find에서도 언급했지만 Union은 집합 두개를 합치는 방법으로 합칠 두 원소의 루트 노드를 찾고 그 노드 두개를 부모 자식 관계로 연결해주면 됩니다. 코드는 아래와 같습니다.
static void union(int a, int b){
int x = find(a, parent);
int y = find(b, parent);
parent[x] = y;
}
두 원소의 루트 노드를 찾고 둘 중 하나의 루트를 다른 루트의 부모로 만들어 줍니다. 자 그럼 한번 생각해봅시다. Union이 이루어지고 해당 집합에 대한 find가 이루어지면 또 경로 압축 과정이 있을 겁니다. 이 경로 압축 과정을 좀 덜 하려면 어떻게 하면 좋을까요?
바로 집합의 크기가 큰 노드를 부모로 만들어주면 됩니다. 자식이 된 부분이 경로 압축이 이루어질 부분이기 때문입니다. 이를 위해서는 집합의 크기를 저장할 배열이 추가로 필요하게 됩니다. size배열이라고 하겠습니다.
집합 {1, 2}과 {3} 이 있고 2, 3을 union하는 순서는 아래와 같습니다.
위의 과정을 코드로 나타내면 아래와 같습니다.
static void union(int a, int b){
int x = find(a, parent);
int y = find(b, parnet);
if(size[x] > size[y])
swap(x, y);
parent[x] = y;
size[y] += size[x];
}
이제 Union-Find를 이용해 문제를 해결해보겠습니다.
통나무에서 통나무로 이동 가능한 조건이 주어집니다. 통나무 N개에 대한 좌표가 주어지고 임의의 통나무 두개를 query로 주어지면 이동이 가능한지를 출력해야하는 문제입니다.
통나무 간의 이동이 가능한 통나무들을 하나의 집합으로 만들어줍니다. query가 주어졌을 때 같은 집합에 포함된 통나무라면 1을 출력해주면 됩니다.
의문이 든다면?
혹시 몇몇 분은 위의 <그림2>와 같은 상황은 어떻게 하냐고 할 수 있습니다. 분명히 통나무 4도 통나무1을 포함하는 집합에 포함되야 하는데 말이죠. 그치만 이런 상황은 통나무1에 대해 통나무 2, 3, 4,,,n까지 보는 과정에서 체크되었기 때문에 걱정하지 않아도 됩니다.
이 부분의 코드
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (nodes[i].x2 >= nodes[j].x1) {
union(nodes[i].idx, nodes[j].idx, parent, size);
} else {
break;
}
}
}
import java.io.*;
import java.util.*;
class Node implements Comparable<Node> {
int x1;
int x2;
int idx;
Node(int idx, int x1, int x2) {
this.idx = idx;
this.x1 = x1;
this.x2 = x2;
}
public int compareTo(Node that) {
if (this.x1 < that.x1) {
return -1;
} else if (this.x1 == that.x1) {
return 0;
}
return 1;
}
}
class baek__17619 {
static int find(int a, int[] parent) {
return a == parent[a] ? a : (parent[a] = find(parent[a], parent));
}
static void union(int a, int b, int[] parent, int[] size) {
int r1 = find(a, parent);
int r2 = find(b, parent);
if (size[r1] > size[r2]) {
int temp = r1;
r1 = r2;
r2 = temp;
}
parent[r1] = r2;
size[r2] += size[r1];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] temp = br.readLine().split(" ");
int n = Integer.parseInt(temp[0]);
int[] parent = new int[n + 1];
int[] size = new int[n + 1];
Node[] nodes = new Node[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
size[i] = 1;
}
int q = Integer.parseInt(temp[1]);
nodes[0] = new Node(-1, -1, -1);
for (int i = 1; i <= n; i++) {
temp = br.readLine().split(" ");
nodes[i] = new Node(i, Integer.parseInt(temp[0]), Integer.parseInt(temp[1]));
}
Arrays.sort(nodes);
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (nodes[i].x2 >= nodes[j].x1) {
union(nodes[i].idx, nodes[j].idx, parent, size);
} else {
break;
}
}
}
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
temp = br.readLine().split(" ");
int u = Integer.parseInt(temp[0]);
int v = Integer.parseInt(temp[1]);
int r1 = find(u, parent);
int r2 = find(v, parent);
if (r1 == r2) {
sb.append(1 + "\n");
} else {
sb.append(0 + "\n");
}
}
System.out.print(sb);
}
}