유니온 파인드(Union-Find) 알고리즘

유니온 파인드(Union-Find) 알고리즘

특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산 + 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산

 

 

유니온 파인드 알고리즘 핵심 이론

• union 연산

각 노드가 속한 집합을 1개로 합치는 연산

void unionfunc(int a, int b)
{
  // a와 b의 대표 노드 찾기
  a = find(a);
  b = find(b);

  if(a != b)
  {
    parent[b] = a;	// 두 원소의 대표 노드끼리 연결
  }
}

 

• find 연산

자신이 속한 집합의 대표 노드를 찾는 연산

int find(int a)
{
  if(a == parent[a])
  {
    return a;	// a가 대표 노드면 반환
  }
  else
  {
    // a의 대표 노드값을 find(parent[a]) 값으로 저장
    return parent[a] = find(parent[a]);	// 재귀 함수 형태
  }
}

 

 

유니온 파인드 알고리즘 구현 방법

1. 1차원 배열을 이용하여 대표 노드를 자기 자신으로 초기화한다.

초기화

 

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

union(1, 4), union(5, 6)

 

- union(1, 4) : 1, 4번 노드의 대표 노드를 찾아 연결

- union(5, 6) : 5, 6번 노드의 대표 노드를 찾아 연결

 

union(4, 6)

 

- union(4, 6) : 4, 6번 노드의 대표 노드를 찾아 연결

  ⇒ 4번과 6번은 대표 노드가 아니므로 find 연산을 이용하여 대표 노드(1, 5)를 찾아 연결

 

 

find 연산의 작동 원리

[ 예시 ]

 

① index값과 value값을 비교한다.

[ 예시 ]

A[6] != 6 ⇒ 다름

A[5] != 5 ⇒ 다름

 

② 동일하지 않으면 value값이 가리키는 index로 이동 후 다시 비교한다.

 

③ 이동 위치의 index값과 value값이 같을 때까지 ①~②를 반복한다.

[ 예시 ]

A[1] == 1 ⇒ 같음

  ⇒ 1번 노드가 집합의 대표 노드

 

④ 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 대표 노드값으로 변경한다.

[ 예시 ]

재귀 함수를 나오면서 그동안 거친 노드의 value값을 1번 노드의 value값으로 변경

 

 

find 연산의 효과

find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 줄인다.

[ 예시 ]

 

find 연산을 할 때 거치는 노드들이 대표 노드와 직접 연결되는 형태로 변경된다.

이러한 형태로 변경되면 이후 find 연산이 진행될 때 연산 속도가 O(1)로 변경되는 경로 압축의 효과가 나타난다.

 

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

 

[ 예시 ]

한 번의 find 연산 이후 find(4) 연산을 수행하면 한 번의 이동으로 바로 대표 노드를 찾을 수 있다.

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>을 참고하였습니다.