[알고리즘] union find 경로 압축

 

유니온 파인드

유니온 파인드에 대해 간단히 설명하면, 

• Union: 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 자료구조에서는 상호 배타적 집합만을 다루므로 Union 연산은 합집한 연산과 같다.
• Find: 하나읜 원소가 어떤 집합에 속해있는지를 판단한다.

 

[백준 1717 문제]

 

일반적인 union, find 알고리즘은 아래와 같다.

int find(int num){
	if (parent[num] == num)
    	return num;
        
    return find(parent[num]); //재귀 형태로 구현
 }
 
 void union(int num1, int num2){
 
 num1 = find(num1);//가장 부모 
 num2 = find(num2);//가장 부모
    
    if (num1 != num2){
    	parent[num1] = num2;
    }
 }

그런데 이렇게 구현했더니, 시간 초과가 나왔다.

 

 

경로 압축

 

경로 압축을 적용해야했던 것.

경로 압축에 대해 알아보기 전에 경로 압축을 하지 않은 경우를 먼저 보자.

 

예제 입력을 사용했다.

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

 

• 처음에는 각 노드 모두 부모 노드 값에 자기 자신 노드 값을 가지고 있다.

• 0 1 3 -> 1과 3을 union 하는 것이므로 parent[3] = 1로 갱신해준다.

• 0 7 6 -> 6과 7을 union하는 것이므로 parent[7] = 6 로 갱신해준다.

• 0 3 7 -> 3과 7을 union하는 것이므로 
  • find(3) = find(1) = 1
  • find(7) = find(6) = 6
  • 두개의 find 결과 값이 다르므로, parent[7] = 1로 갱신해서 두 서로 다른 집합을 연결해준다.

그런데, 이런식으로, find를 여러번 타고 들어가는 것은 재귀함수를 계속 호출하는 것이기 때문에

트리의 길이(깊이)가 커지면 성능저하를 일으킬 수 있다. 시간 초과가 걸리는 것이다.

 

적용

 

경로 압축은 간단하다.

기존 find 함수를 호출할때, 노드의 값이 부모 노드가 아닌 경우, 

부모 노드의 값으로 대체하며 재귀를 호출하는 것이다. 

 

int find(int num){
	if (parent[num] == num)
    	return num;
        
    return parent[num] = find(parent[num]); //재귀 형태로 구현
 }

이렇게 되면, 경로 압축을 적용하지 않았을 때보다

find함수의 호출 수가 적어지면서, 시간 초과를 방지할 수 있다.

 

 

코드

 

package 알고리즘_코딩테스트.dayone.mar17;

import java.io.*;
import java.util.*;

public class BOJ_1717 {
    static int n, m;
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    static int[] parent;

    public static void main(String[] args) throws IOException {
        input();
        System.out.println(sb);
    }

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken()); // 정점의 수
        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(bf.readLine());
            int check = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (check == 0) {
                union(a, b); // union 연산
            } else {
                find(a, b); // find 연산
            }
        }
    }

    // Union 함수: 두 노드를 같은 집합으로 합침
    private static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA != rootB) {
            if (rootA < rootB) {
                parent[rootB] = rootA; // rootA가 더 작으면 rootB의 부모를 rootA로 설정
            } else {
                parent[rootA] = rootB; // rootB가 더 작으면 rootA의 부모를 rootB로 설정
            }
        }
    }

    private static int find(int num){
        if (parent[num] == num)
            return num;

        return parent[num] = find(parent[num]); //재귀 형태로 구현
    }


    // Find 함수: 두 노드가 같은 집합에 속하는지 확인
    private static void find(int a, int b) {
        int num1 = find(a);
        int num2 = find(b);

        if (num1 == num2) {
            sb.append("YES\n"); // 같은 집합이면 YES
        } else {
            sb.append("NO\n"); // 다른 집합이면 NO
        }
    }
}

참고

[유니온 파인드]

[백준 1717 문제]