[그래프/트리 - 응용] Union-Find / 서로소 집합

Union-Find란?

---

백준 문제를 풀 때 DFS로 풀었던 문제를 다른 사람들은 Union-Find로 풀었길래 정리.

 

11724번: 연결 요소의 개수

 

 

 

Union-Find 알고리즘

• 대표적 그래프/트리 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있다.
• 상호 배타적 집합(Disjoint-set)이라고도 하며 서로소 집합으로 불린다.
  • 서로소인 부분 집합의 표현
• 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.
• 2가지 연산으로 이루어져 있다.
  • Find : x가 어떤 집합(그래프)에 포함되어 있는지 찾는 연산.
  • Union: x와 y가 포함되어 있는 집합을 합치는 연산
    • 원소 x와 y를 합친다는 뜻은 x와 y의 부모를 같은 원소로 만든다는 것이다.

 

 

Union-Find 예시

---

 

위와 같이, 모두 연결되어 있지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신을 가리키도록 만든다.

• i : 노드 번호
• Parent[i] : i가 어떤 부모 노드에 속해 있는 

즉, 자기 자신이 어떤 부모에 포함되어 있는지를 의미한다.

Parent[i] = i로 표현할 수 있다.

 

 

 

Union(1,2); Union(3,4) 를 해주어 위와 같이 노드를 연결해보자.

위와 같이 표에 표현이 된다. 2번째 인덱스에 '1'이 들어가고, 4번 인덱스에 '3'이 들어가는 것으로 각각의 부모 인덱스를 갖고 있다.

• parent[2] = 1
• parent[4] = 3

이와 같이 부모를 합칠 때는 일반적으로 노드 번호가 작은 쪽이 부모가 되도록 한다. 이것을 Union 과정이라고 한다.

 

 

또 다른 예시로 위와 같이 1, 2, 3이 연결될 때는 바로 아래와 같이 표현이 된다.

 

1과 3은 부모가 다르기 때문에 '1과 3이 연결되었는지' 파악하기 힘들다. 이는 재귀함수가 사용된다.

3의 부모인 2를 먼저 찾고, 2의 부모인 1을 찾아, 결과적으로 3의 부모는 1이 되는 것을 파악하는 것이다.

• parent[3] = find(parent[3]) . 이때 parent[3] == 2이므로 find(2).
• parent[2] = find(parent[2]) . 이때 parent[2] == 1이므로 find(1).
• find(1)은 1을 갖고 있기 때문에 결국 재귀적으로 parent[3] = 1이 된다.

Union(1,3)의 과정이 수행된 후에는 다음과 같은 표가 된다.

 

 

결국 1,2,3의 부모는 모두 1이기 때문에 이 세 가지 노드는 모두 같은 그래프에 속한다는 것을 알 수 있습니다.

해당 경로를 바꿔주는 과정은 아래와 같은 그림으로 변하게 됩니다.

 

 

 

Union-Find 함수

---

find 함수의 소스코드

public static int find(int x) {
       if(parent[x] == x)
           return x;
       else
          return parent[x] = find(parent[x]);
}

find 함수는 매개변수로 받은 원소 x의 부모 노드가 누구인지를 찾아주는 함수이다. 만약 x의 부모가 x이라면 그대로 x를 리턴하면 된다. 만약 아니라면 x의 부모를 다시 find 함수에 보내 재귀 호출을 하여 x의 부모를 찾게 된다.

 

 

union 함수의 소스코드

public static boolean union(int x, int y) {
    x = find(x); //x의 부모노드 찾기
    y = find(y); //y의 부모노드 찾기
    
    // 이미 같은 그래프에 속해있을 때 false 반환
    if(x == y) return false;
    
    if(x <= y) parent[y] = x;
    else parent[x] = y;
    return true;
}

union 함수는 매개변수로 받은 원소 x와 y를 같은 그래프로 합치는 함수이다. 이를 위해 먼저 x와 y의 부모를 찾는 과정을 거쳐야 한다. x와 y의 부모를 find 함수를 통해 찾은 뒤 만약 부모가 같다면 같은 그래프에 속해 있으므로 False를 반환한다.

부모가 다르다면 x, y 중 노드 번호가 작은 쪽이 부모가 되도록 한다.

매개변수로 전달해주는 값들의 비교가 확실하다면 !=로도 가능하다.

​

 

전체코드

public class Main {
    static int[] parent;
 
    // union 연산
    public static boolean union(int x, int y) {
        x = find(x);
        y = find(y);
        
        if(x == y) return false;
        
        if(x <= y) parent[y] = x;
        else parent[x] = y;
        return true;
    }
    
    // find 연산
    public static int find(int x) {
        if(parent[x] == x) return x;
        return find(parent[x]);
    }
    
     // parent 출력
    public static void parentPrint() {
        System.out.print("[ ");
        for (int i = 1; i < parent.length; i++) {
            System.out.print(parent[i]+ " ");
        }
        System.out.println("]");
    }
 
    public static void main(String[] args) {
        int n = 5;
        parent = new int[n + 1];
        // 부모 노드 초기화
        for (int i = 0; i < parent.length; i++) parent[i] = i;
        
        //위의 예제 실행
        union(1, 2);
        parentPrint();
        union(3, 4);
        parentPrint();
        union(3, 5);
        parentPrint();
        System.out.println("find(2): " + find(2));
        System.out.println("find(4): " + find(4));
        union(2, 4);
        parentPrint();
        System.out.println("find(4): " + find(4));
    }
}

 

 

 

 

 

 

---

참고)

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9CUnion-Find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#-%EB%AA%A9%EC%B0%A8https://kistone.tistory.com/58

https://m.blog.naver.com/parkhj2416/221861837543