Union-Find 알고리즘

코딩테스트 문제를 풀다보면 간혹 다른 풀이로 등장하는 유니온 파인드에 대해서 공부하기 위한 포스트..
어렴풋이 알고리즘 수업 때 배웠던 것 같은데 잘 기억이 안나서 다시 공부했다
블로그로만 공부하기엔 이해가 잘 안돼서 유튜브 강의를 참고했다

Union-Find는 그래프 이론에 속하는 알고리즘 중 하나이고 집합의 개념과 tree의 개념을 함께 사용한다
유니온 파인드를 사용하면 서로소 집합 자료구조를 만들 수 있다. 집합에서 노드들을 합치고, 노드들의 최종 부모(root)를 찾아 서로소 집합을 찾는다

유니온 파인드는 두 개의 연산으로 나뉘는데, 그 중 유니온 연산은 두 개의 집합을 하나의 집합으로 합치는 연산이다(합집합)

1	2	3	4	5	6
1	2	3	4	5	6

만약 서로서로 연결되지 않고 자기 자신만을 원소로 갖는 집합이 있다면 위와 같이 리스트로 표현할 수 있다
인덱스는 노드 번호를 의미하고, 리스트의 원소는 해당 노드의 부모 노드 번호이다
이 경우에는 자기 자신만을 원소로 갖기 때문에 부모 노드도 자기 자신이 된다

만약, 이 때 1번 노드와 2번 노드를 합친다면, 즉 유니온 연산을 수행한다면 1번 노드와 2번 노드는 엣지를 통해 연결되게 될 것이다
또한 보통 노드번호가 작은 것을 부모노드로 정한다고 하므로, 리스트는 다음과 같이 변하게 될 것이다

1	2	3	4	5	6
1	1	3	4	5	6

여기서 2번 노드와 3번 노드를 또 합치게 되면, 다음과 같은 결과를 얻게 된다

1	2	3	4	5	6
1	1	2	4	5	6

이 상태에서는 3번 노드의 최종적인 부모노드(root)가 무엇인지는 명확하지가 않다
이 때, 해당 트리(집합)의 루트노드를 찾는 Find함수가 사용된다
Find 함수는 재귀 함수 형태로, root 노드를 찾을때까지 재귀적으로 호출된다
root 노드는 부모노드가 자기 자신이기때문에 노드 번호와 부모 노드 번호가 동일한 노드가 곧 해당 집합의 root 노드가 된다
결과적으로, Find 함수 수행을 통해 3번 노드의 root노드가 1번 노드라는 사실을 알 수 있게 된다

import sys

# root 노드 찾기
def find_parent(parent, x):
	if parent[x] != x:
    	parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 집합을 합치기
def union_parent(parent, a, b):
	a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
    	parent[b] = a
    else:
    	parent[a] = b

# 노드와 간선의 개수
n, e = map(int, sys.stdin.readline().split())
parent = [i for i in range(n+1)]

# 연결된 노드끼리 합치기
for _ in range(e):
	a, b = map(int, sys.stdin.readline().split())
    union_parent(parent, a, b)

# root 노드 찾기(서로소 집합으로 나누기)
for i in range(1,n+1):
	print(find_parent(parent, i), end=" ")