<Union-Find> BOJ 17619 개구리 점프

Union-Find에 대한 개념 설명부터 있습니다. 이미 알고 계신다면 아래 문제 부분부터 보시면 되겠습니다.

Union-Find란?

Union-Find는 자료구조 트리를 활용해 집합을 표현하는 자료구조이며 집합간의 합치거나(Union) 원소가 어느 집합에 포함되어 있는지를 찾는(Find) 연산이 매우 빠른 것이 특징입니다.

빠르게 찾는 다는 것은 최적화가 이루어졌을 때 대부분의 경우에서 상수 시간의 복잡도를 보이게 됩니다

Find

Union-Find의 시작은 대부분 원소 한개로 이루어진 여러개의 집합으로 시작합니다.

• {1}, {2}, ... {n}

이러한 집합을 1차원 배열에 저장해 주도록 하겠습니다. parent라는 배열을 만들고 자기 자신을 parent로 지정해주면 됩니다. 부모 노드를 의미하게 됩니다.

• parent[1] = 1, parent[2] = 2, ... parent[n] = n

만약 1을 루트로 갖는 집합과 2를 루트로 갖는 집합을 합친다고 하면 둘 중 하나의 루트를 다른 루트의 자식으로 연결해주면 됩니다.(결국 이게 Union인데 아래에서 더욱 자세히 설명하도록 하겠습니다.) 합친 결과로 아래처럼 되겠네요.

• parent[1] = 1, parent[2] = 1, ... parent[n] = n

자 그럼 이 상황에서 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의 시간 복잡도는 $O(N)$이 됩니다. 왜냐하면 아래와 같은 상황이 있을 수도 있기 때문입니다.

그러면 이 복잡도를 줄이기 위해서 어떤 방법이 있을까요?

경로 압축

바로 경로 압축이란 방법을 사용할 수 있습니다. 경로 압축의 아이디어는 바로 집합의 모든 노드의 부모를 루트 노드로 바꾸는 겁니다. 이걸 하기 위한 코드는 매우 간단합니다.

static int find(int x, int[] parent){
  return parent[x] == x? parent[x] : (parent[x] = find(parent[x]);
}

위의 경로 압축 전 코드에서 parent[x] = find(parent[x])만 수정해주었습니다. 결국 쭉쭉 타고 올라가면서 모든 노드의 parent를 루트 노드로 바꾸게 됩니다.

Union

Find에서도 언급했지만 Union은 집합 두개를 합치는 방법으로 합칠 두 원소의 루트 노드를 찾고 그 노드 두개를 부모 자식 관계로 연결해주면 됩니다. 코드는 아래와 같습니다.

static void union(int a, int b){
  int x = find(a, parent);
  int y = find(b, parent);
  
  parent[x] = y;
}

두 원소의 루트 노드를 찾고 둘 중 하나의 루트를 다른 루트의 부모로 만들어 줍니다. 자 그럼 한번 생각해봅시다. Union이 이루어지고 해당 집합에 대한 find가 이루어지면 또 경로 압축 과정이 있을 겁니다. 이 경로 압축 과정을 좀 덜 하려면 어떻게 하면 좋을까요?

small to large

바로 집합의 크기가 큰 노드를 부모로 만들어주면 됩니다. 자식이 된 부분이 경로 압축이 이루어질 부분이기 때문입니다. 이를 위해서는 집합의 크기를 저장할 배열이 추가로 필요하게 됩니다. size배열이라고 하겠습니다.

집합 {1, 2}과 {3} 이 있고 2, 3을 union하는 순서는 아래와 같습니다.

1. 사이즈는 다음과 같다. size[2] = 2, size[3] = 1
2. 루트를 찾는다. find(2) = 1, find(3) = 3
3. 합친다. parent[3] = 1, size[2] += size[3]

위의 과정을 코드로 나타내면 아래와 같습니다.

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로 주어지면 이동이 가능한지를 출력해야하는 문제입니다.

• 통나무의 개수 N <= 100000
• query의 개수 Q <= 100000

접근

통나무 간의 이동이 가능한 통나무들을 하나의 집합으로 만들어줍니다. query가 주어졌을 때 같은 집합에 포함된 통나무라면 1을 출력해주면 됩니다.

• 집합 구성 과정
  만약에 모든 통나무를 이중 포문 으로 돌아주면서 두 통나무가 이동 가능할때마다 두 집합을 union해준다고 하면 약 100억의 시간 복잡도를 갖습니다. 당연히 안되겠죠..
• 정렬을 해주자
  자 이럴 때 먼저 x1을 기준으로 통나무 배열을 정렬해줍니다. 정렬된 순서에서는 뒤의 통나무의 시작점이 앞의 통나무의 시작점보다 작은 값을 갖는 일은 없게 됩니다. 이렇게 되면 뒤 통나무의 시작점이 앞 통나무의 끝점보다 커지게 되면 그 뒤 통나무부터는 더이상 보지 않아도 됩니다. 일종의 백트래킹이죠.. 사실 정확히 어느 정도의 시간 복잡도를 갖는지는 예상 못했지만.. proof of AC라고 하죠.. 맞더라구요.. 그러므로 증명 완료.! 시각적으로 나타내면 아래의 <그림1>과 같습니다. <그림1>과 같은 상황에서 통나무3부터는 통나무1이나 통나무2와 더이상 같은 집합이 될 수 없죠.

• 의문이 든다면?
  혹시 몇몇 분은 위의 <그림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);
    }
}