유니온 파인드

유니온 파인드

유니온 파인드 (Union-Find) : 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘

그래프를 합치는 Union 연산과 루트 노드를 찾는 Find 연산으로 이루어져있다.

항상 써야 할 때마다 직접 구현하다 보면 시간이 좀 걸려서 전체적인 틀 자체는 외워두는 것이 좋다고 판단하여 정리한다.

우선 노드 별로 자신의 부모 노드를 저장하는 배열(parents)을 선언한다.
초기 부모 노드의 값은 자기 자신이다. 이후 Find와 Union을 구현한다.

Find 연산

def find(x) {
	if x == parents[x]:
    	return x
    parents[x] = find(parents[x])
    return parents[x]
}

가장 눈여겨 보아야 할 점이 루트 노드를 탐색하면서 그와 동시에 parents 배열을 업데이트 한다는 점이다. 이를 통해 루트 노드를 접근하는데 필요한 시간을 줄일 수 있다. 이를 경로 압축이라고도 부른다.

Union 연산

def union(x,y) {
	x = find(x)
    y = find(y)
    if x != y:
    	parents[y] = x
}

두 노드를 합치는 연산에서는 우선 두 노드의 루트 노드를 찾는다. 루트 노드가 같다면 이미 합쳐져 있는 상태이기 때문에 고려할 필요가 없고, 다르다면, 한 노드의 루트 노드를 다른 노드의 루트 노드로 설정한다. 이제 두 노드는 같은 루트 노드를 가지고 있기 때문에 한 그래프에 속한다고 볼 수가 있다!