『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

유니온 파인드 (Union-Find)

• 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지 확인하는 find 연산으로 구성되어 있는 알고리즘이다.

핵심 이론

• 유니온 파인드는 union, find 연산을 완벽히 이해하는 것이 핵심이다.

union 연산

• 각 노드가 속한 집합을 1개로 합치는 연산이다.
• 노드 a, b가 $a \in A$, $b \in B$일 때 union(a, b)는 $A \cup B$이다.

find 연산

• 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다.
• 노드 a가 $a \in A$일 때 find(a, b)는 A 집합의 대표 노드를 반환한다.

💡 단순히 대표 노드를 찾는 역할만 하는 것이 아니라, 그래프를 정돈하고 시간 복잡도를 향상시킨다.

구현 방법

1. 유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것이다.

   • 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다.
   • 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스값으로 초기화한다.

   int[] array = new int[5];
   array[1] = 1;
   array[2] = 2;
   array[3] = 3;
   array[4] = 4;

2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행한다.

   • 대표 노드는 작은 값으로 설정한다고 하자.
   • 이때, 대표 노드끼리 연결해야 한다.
   • 만약 1과 4를 연결하려면 array[4] 의 대표 노드값을 1로 변경한다.

   // union(1, 4)
   array[4] = 1;
   
   // union(5, 6)
   array[6] = 5;
   
   // union(4, 6) -> 대표 노드인 1과 5를 연결한다.
   array[5] = 1;

find 연산의 작동 원리

1. 대상 노드 배열에 index 값과 value 값이 동일한지 확인한다.
2. 동일하지 않으면 value 값이 가리키는 index 위치로 이동한다.
3. 이동 위치의 index 값과 value 값이 같을 때까지 1~2번 과정을 반복한다.
   • 반복되므로 이 부분은 재귀 함수로 구현한다.
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드로 변경한다.

• 한 번의 find 연산을 이용해 모든 노드가 루트 노드에 직접 연결되는 형태로 변경된다.
• 이러한 형태로 변경되면 이후 find 연산이 진행될 때 경로 압축의 효과가 나타난다.

💡 경로 압축은 실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형해 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법을 말한다.

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런