1. Union-Find

Union-Find(유니온-파인드)

유니온 파인드 알고리즘은 서로소 집합을 찾는 알고리즘이다.

주로 아래와 같은 상황에서 사용할 수 있다.

여러 가지 데이터가 존재할 때
- 이 데이터들이 몇 개의 집합으로 묶여 있는지 파악.
- 무작위로 두 개의 데이터를 뽑았을 때, 두 데이터가 같은 집합의 원소인지 / 서로 다른 집합인지 파악.

위 두 경우만 봐도 서로소 집합을 찾을 때, 사용한다는 말이 와닿는다.

사실, 구체적으로는 그래프 알고리즘이다.

어떤 원소가 어떤 같은 그래프에 속하는지, 또는 서로 다른 그래프인지를 구별하는 방법인데,

아래 그림과 같다.

위 그래프를 보시면, 두 개의 그래프가 있습니다. {1,2,3,6,7}과 {4,5}로 두 그래프로 나뉘어 있다.

만약 이러한 그래프에서 "3과 4가 같은 그래프인가"라고 묻는다면 "False"라고 답 할 수 있을 것이며,

"몇 개의 그래프로 나누어지느냐"라고 묻는 다면 2라고 답할 수 있게 되는 것이다.

구현 방법

구현하는 방식에 대해 설명해보자. 우선, 아래와 같이 배열을 초기화한다.

(0번 인덱스는 생략.)

각 인덱스 번호에 맞게 값을 초기화.

여기서부터는 union과 find라는 것을 따로 생각할 것이다.

union은 두 데이터를 결합해 주는 기능, find는 한 데이터가 최종적으로 어떤 데이터와 연결되어 있는 지를 알려주는 기능이다.

1번부터 연결 지어보도록 하자. 1번은 2번만 연결되어 있으므로, union(1,2)을 수행하게 된다. 수행한 결과는 아래와 같이 될 것이다.

연결이 되고 나면, 1번과 2번은 같은 그래프임을 표시해야 하기 때문에, 처음에 만든 배열에 손을 댈 것이다.

배열의 1번 인덱스의 값이 2로 바뀜으로써, 데이터 1은 2라는 데이터에 묶인 것이다.

그다음으로 2번 인덱스의 값이 6과 연결되어 있으므로 union(2,6)을 수행한다.

위와 같이 반복 수행을 통해 하나의 그래프를 완성시킬 수 있다.

그리고, 위 그래프가 완성되면 배열은 아래와 같아질 것이다.

3을 기준으로 하여, 1,2,6,7이 하나의 그래프로 묶인 것을 알 수 있다.

이러한 결과를 통해서 "2와 7이 같은 그래프(집합)이냐?"라고 묻는다면 find(2)와 find(7) 이 같은 값을 가지고 있는지 확인한 후에 TRUE라고 알려줄 수 있다.

위와 같은 방식으로 4와 5도 union(4,5)를 통해 결합을 하면 최종적으로 아래와 같이 완성된다.

소스코드(Java)

import java.util.*;

class Main {

    static int[] arr;

    // union()을 통한 두 데이터 결합하는 메소드
    static void union(int a, int b) {
        int findA = find(a);
        int findB = find(b);

        if(findA != findB) arr[findA] = findB;
    }

    // 특정 데이터가 어떤 값으로 묶여있는 지 확인할 수 있는 메소드
    static int find(int a) {
        if(a == arr[a]) return arr[a];
        else
            return arr[a] = find(arr[a]);
    }


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

		
        arr = new int[n+1]; 
        for(int i=0; i<=n; i++) {
            arr[i] = i;
        }
        
        
        for(int i=0; i<m; i++) { 
            int s = sc.nextInt(); 
            int k = sc.nextInt();

            union(s, k); // 입력 받은 두 데이터를 union()호출하여 결합.
        }

		
        (find(2) == find(5)) // False  3 != 4
        (find(2) == find(7)) // True   3 == 3

    }
}

find(int a)
- 초기에 각 인덱스 번호와 일치하게 값을 초기화시킨다..
- 그러므로 a와 arr[a]가 일치하지 않다는 것은 현재 a라는 값이 다른 값(arr [a])에 의해 묶였다는 뜻과 같다.
- 그래서, 재귀를 통해 arr[a]를 인덱스로 가지는 위치로 찾아간다. --> find(arr[a])
- 그리고, return과 동시에 arr[a] 값을 새로운 값으로 바꾸어 준다.
- 예를 들어, 위 예제 그래프에서 1과 3이 동일한 그래프인지 확인해야 한다고 가정한다.
  - find(1)과 find(3)을 각각 수행하여 결과가 동일한 지 확인한다.
  - find(1)을 수행하면 인덱스 1과 값 3은 일치하지 않으므로, find(3)을 수행하여 return 한다.
  - find(3)은 인덱스 3과 값 3이 동일하므로 3이라는 값을 reuturn 한다.
  - 여기서 중요한 점이, return과 동시에 arr[1]을 3이라는 값으로 변경하는 것이다.(arr[1] = find(arr[3]) )
  - 그리고, find(3)을 수행하여 find(1)과 같은 3을 리턴하므로 동일한 그래프임을 알 수 있다.

union(int a, int b)
- 데이터 a와 b가 각각 어떤 값으로 묶여있는지 확인하기 위해 find(a), find(b)를 각각 수행한다.
- find(a)와 find(b)가 같지 않다면 묶여있지 않는 것이므로,
  arr[findA] = findB를 통해 묶어준다.
  예를 들어, 위 예제 그래프에서 3과 5가 묶여 있었더라면 union(3,5)를 수행하면 다음과 같은 일이 발생한다.
  - find(3)을 통해서 3을 가져온다.
  - find(5)를 통해서 4를 가져온다.
  - 두 값이 일치하지 않으므로, arr[3]에 4라는 값을 넣어준다.
  - 이렇게 됨으로써, 4라는 값으로 3(3을 값으로 가지고 있던 다른 데이터들도 포함)이 묶이게 되는 것이다.

'알고리즘 > 개념정리' 카테고리의 다른 글

2. 플로이드 와샬 (0)	2023.03.02

기억 안 나면 다시 보면 되지

1. Union-Find