[알고리즘] Union -Find

백준 공항 문제를 풀다가 Union - Find가 무엇인지 모르겠어서 공부한 내용을 정리해보려 한다. 

 

Union - Find란?

Disjoint set을 표현할 때 사용하는 알고리즘 

 

트리구조를 이용해 구현하는 것이 제일 효율적이다 

 

함수

• union(x, y) : x가 속한 집합과 y가 속한 집합을 합친다 
• find(x) : x가 속한 집합의 루트노드 값을 반환한다 
• 재귀함수를 이용하는데, 루트노드가 들어온 경우는 그거 그대로 반환하고, 
• 아닌경우는 부모노드를 계속 찾아서 반환한다 

 

초기화는 

parents=[i for i in range(g+1)] 방식으로 하면 된다 

 

공항 문제에서는 1번부터 gi까지의 게이트 중 빈 게이트를 이용하면 되므로, i번째 비행기의 게이트 값이 부모 루트가 되어서, 

그거에 속한 애들을 구하는 알고리즘이 필요해서 union - find를 이용한 것이라고 이해했다. 

그래서 같은 게이트 번호를 가진 비행기들을 최대한 도킹시킬 수 있다. 

 

참고 블로그 : https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html