[단계별로 풀어보기] - 유니온 파인드

Union Find는 각 대상들이 어떤 집합에 속하는지에 대해 파악하는 알고리즘이다. 

하나의 배열로, 각 대상이 index로, value가 parent, 즉 해당 집합을 대표하는 number로 지정된다. 

 

처음 초기화는, parent[i] = i 로 해주고

parent를 찾는 건 배열에 대한 탐색을 재귀적으로 찾되, 재귀적으로 찾은 결과를 현재 값에 적용시켜야 한다. 

return parent[n] = find_parent(parent[n]) 가 최적화의 핵심이라고 할 수 있다. 

 

공항 문제는, 문제 자체가 이해가 되지 않아서 미루었다.