[Do it!_Algorithm with Python] 5.3 Union-Find

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python'

 

 

Union-Find는 말 그대로 두개의 연산으로 구성되어 있는 알고리즘이다.

 

▪️수학적 연산 기법

▷ Union 연산: 각 node가 속한 집합을 1개로 합치는 연산.

  node a, b가 각각 집합 A,B에 속할 때, union(a,b)는 A U B를 말한다. 우리가 집합연산에서 배웠던 합집합과 같다.

 

▷ Find 연산: 특정 노드 a가 속한 집합의 대표 node를 반환해준다.

  노드 a가 A집합에 속할 때, find(a) 는 A집합의 대표 노드(루트 노드)를 반환한다.

 

 

 

▪️그림으로 과정 이해하기

union-find는 집합을 표현하는 배열, 리스트, 트리로 표현할 수 있지만, 우선 빠른 이해를 위해 1차원 배열로 살펴보자.

 

1) 배열 초기화

 

처음에는 자신의 index값으로 초기화

처음에는 어떠한 노드도 서로 연결되어 있지 않다. 이 경우 자기 자신이 대표 노드가 되므로 자신의 index 값으로 배열을 초기화 한다.

 

 

2) 2개의 노드 선택 후 union 연산 수행

 

 

① union(1,4) 는 노드 1과 4를 그래프에서 선으로 연결한다는 것과 같다.

이때 대표노드를 숫자가 더 작은 노드로 선택한다고 할 때, 1과 4의 대표노드는 1이 되므로 노드 4의 배열 값을 1로 업데이트 한다.

② union(5,6) 도 마찬가지이다.

 

🔻union 연산을 할 때 주의할 점이 있다.

union으로 두 집합을 합칠때는 항상 각 집합의 대표 노드끼리 연결해 준다! 

 

③ 따라서 union(4,6)를 계산할 때는 find(4), find(6)으로 각각의 대표 노드를 찾고 그 노드를 연결해주어야 한다.

 

- find(4) = (node 4가 속한 집합의 대표 노드인 node 1)

- find(6) = (node 6이 속한 집합의 대표 노드인 node 5)

 

따라서 node 1과 5를 연결해주면, 원칙대로 숫자가 작은 node 1이 전체 집합의 대표 노드가 되므로

node 5의 배열값을 1로 업데이트 해준다.

 

 

 

 

이때 find 연산을 자세히 살펴보자

 

🔻find 연산 (대표 노드 찾기)

역할	작동 원리	예시
- 자신이 속한 집합의 대표 노드 찾기 - 그래프 정돈 - 시간 복잡도 향상	1) 대상 노드 배열에 Index 값이 value 값과 동일한가? 체크 2) 동일하지 않으면 value가 가리키는 index 위치로 이동 3) index 값 = value 값 이 만족할때까지 반복한다 => 반복이므로 재귀함수로 구현 4) 대표노드에 도달하면 재귀함수 빠져나오기 5) 이때 빠져나오면서 거치는 모든 노드 값을 루트 노드값(대표 노드의 value)으로 변경	1) node 6에 6이 들어있는가?  2) 5가 들어있으므로 대표 노드가 아니다. 3) node 6가 갖고있는 값(5)의 index 로 이동한다. 4) index 5에 value 1이 들어있으므로, 다시 재귀함수를 이용하여 위 과정을 반복한다.  4) index 1에 가보면 value 1을 가지므로 대표노드에 도달했다.  5) 재귀함수를 빠져나오면서 노드 5와 6을 거치게 되고, 이때 값들을 index 1(루트노드)의 값이었던 1로 업데이트 해준다.

 

 

 

 

 

▪️Union-find 의 목적은 뭘까?

 

 

union-find는 어떤 모르는 두 노드가 하나의 집합에 속하는지 (연결되어 있는지)만 확인한다.

이때 어떠한 경로,방법으로 연결되어 있는지는 중요하지 않다.

 

그렇다면 위 그래프에서 아래 그래프로 바꾸어주면 어떤 점이 좋을까?

 

위 그래프에서는 node 6에서 대표 노드를 찾아야 할 때, 6->5->4->3->2->1 을 모두 거쳐야 한다. (시간복잡도 O(N))

하지만 아래 그래프에서는 바로 6->1로 한번에 찾을 수 있어서 시간복잡도가 더 좋다. (시간복잡도 O(1))

 

이를 경로 압축이라고 한다.

원래 여러 노드를 거쳐야 대표 노드로 갈 수 있었던 경로를, 그래프를 변형하여 더 짧은 경로로 갈 수 있게 하여

시간복잡도를 줄이는 방법이다.