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

유니온 파인드란?

유니온 파인드는 여러 노드가 있을 때 특정 2개의 노드를 연속적으로 연결하여 하나의 집합으로 묶는 union 연산과 특정 노드의 루트 노드를 찾는 find 연산으로 이루어진 알고리즘입니다.

유니온 파인드는 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘으로, 집합 관계를 판별할때 주로 사용합니다. 그리디 알고리즘 중 하나인 크루스칼 알고리즘에서도 사이클을 판별하기 위해 사용합니다.

 

---

 

예시

• 7개의 섬이 있다고 가정해보겠습니다. 각 섬은 다리로 연결되어 있어, 연결된 섬끼리는 자유롭게 이동할 수 있습니다.
• 즉, 섬 4 - 3 - 5 는 각 섬끼리 다리로 연결되어 있기 때문에 같은 집합이라고 보는 것이죠. 반대로 섬 1에서 4로는 갈 수 없기 때문에 다른 집합으로 생각합니다.
• 이러한 집합의 개념을 union find 에서는 배열에 값을 저장하여 나타냅니다.

 

 

• union find 알고리즘으로 집합을 표현한 모습입니다.
• int 형 배열 각 인덱스에 값을 갱신해주면서 같은 값이면 같은 집합으로 분류합니다.
  
  • 집합 - 1 {1, 2}  /  집합 - 3 {3, 4, 5}  /  집합 - 6 {6, 7}
• unionfind에서는 노드 N의 집합관계를 구할 때 int[] 배열에 접근하여 값을 얻는것이 아닌, find 알고리즘을 사용합니다.

 

 

find 연산

private int find(int a) {
    if (union[a] == a) return a;
    
    // 재귀함수 호출
    // 거쳐간 모든 노드의 집합을 갱신함 -> 시간 복잡도 ↓
    return union[a] = find(union[a]);
}

•  find 연산은 노드가 어느 집합에 소속되어 있는지 판별할 수 있는 값을 반환합니다.
• unionFind[n] != n 이라면 재귀함수를 통해 unionFind 배열의 인덱스와 저장된 값이 같아질 때까지 반복하고 값을 반환합니다.
• 재귀를 통해 집합을 탐색하는 과정에서 거쳐간 모든 노드의 값을 갱신해주면서 시간 복잡도를 줄입니다.
  • ex) 위 예시에서 find(5) = 3 

 

union 연산

Union 연산은 두 노드 A, B를 하나의 집합으로 묶는 연산입니다. find 연산을 사용하여 두 집합관계를 묶습니다.

앞서, 예시로 보여드린 집합관계를 union 연산을 통해 나타내어보겠습니다.

 

int[] union 배열 초기화

int[] union = new int[n + 1];

// union 배열 초기화
for (int i = 1; i < union.length; i++) {
    union[i] = i;
}

• 모든 노드에 대해 각 인덱스의 값을 저장하는 int 형 배열을 생성하고 초기화합니다.

 

 

Union 연산 수행

- 예시 코드 - 

// 섬 연결 정보
int[][] islands = {{1, 2}, {4, 5}, {3, 4}, {6, 7}};

for (int i = 0; i < islands.length; i++) {
    int A = islands[i][0];
    int B = islands[i][1];

    if (find(A) != find(B)) {
       union(A, B);
    }
}

private void union(int a, int b) {
    int A = find(a);
    int B = find(b);

    if (A != B) union[B] = A;
}

private int find(int a) {
    if (union[a] == a) return a;
    // 거쳐간 모든 노드의 집합을 갱신함 -> 시간 복잡도 ↓
    return union[a] = find(union[a]);
}

 

 

• 먼저 1과 2를 묶어보겠습니다. 우선 두 노드에 대해 find 연산을 수행합니다.
  • find 연산은 인덱스와 값이 동일하면 반환해주기 때문에 find(1) = 1, find(2) = 2 입니다.
• 두 값이 다르다면 다른 집합으로 판단하여 union 배열의 값을 갱신합니다.
  • union[2] = 1;

 

 

• 이제 4와 5를 묶어주겠습니다. 앞선 과정과 동일하게 find(4) 의 값과 find(5)의 값을 비교하여 다르다면 union 배열의 값을 갱신해줍니다.
  • 집합 - 1 {1, 2}  /  집합 - 4 {4, 5}

 

 

• 3와 4를 묶어주겠습니다. 앞선 과정과 동일하게 find(3) 의 값과 find(4)의 값을 비교하여 다르다면 union 배열의 값을 갱신해줍니다.
• 이제 3,4,5 는 같은 집합이 되었습니다. 여기서 union 배열에 들어있는 값은 각각 (3, 3 ,4)로 다른 것을 확인할 수 있습니다. 하지만 find 연산을 이용하면 결국 노드 3, 4, 5는 같은 값을 반환하게 됩니다.

 

 

• find 연산은 union 배열의 index와 저장된 값이 같지 않다면 재귀 호출을 통해 값을 탐색합니다.
• 이 과정을 통해 union[5]에는 4가 저장되어있지만, find(5) 는 3을 반환하게 됩니다.
  • 이 때, 거쳐간 노드의 union 배열 값을 갱신해주면 다음과 같이 같은 값을 저장하게 됩니다. 

 

 

 

 

결과 

• 위와 같은 과정을 모두 거치면 다음과 같이 나타낼 수 있습니다.
• find 연산을 통해 union 배열을 탐색하여 같은 집합인지 알 수 있습니다.
• 또한, 같은 집합 내에서 두 노드를 연결하면 사이클이 생기기 때문에 사이클 생성 유무를 판별하기위해 사용되기도 합니다.