분리 집합1 유니온 파인드 (Union Find) 혹은 분리 집합 (Disjoint Set) 유니온 파인드 알고리즘은 같은 집합에 속한 원소들을 O(1)의 시간 복잡도로 확인하는 방법으로 다양한 문제들에서 많이 사용됩니다. 특정 노드는 자신의 부모를 의미하는 P[node] 배열값을 갖습니다. 즉 P[node] = node 인 경우 자기 자신을 부모로 한다는 의미이며, P[node] != node 인경우 다른 노드 번호를 부모로 한다는 뜻입니다. 그럼 대체 이걸 어디에 사용할 수 있을까요? 예를 들어 1번 노드와 3번 노드가 연결되어 있고, 2번 노드와 3번 노드가 연결되어 있다면 1번과 3번이 연결되어있는 것을 알 수 있습니다. 여기서 연결된 노드간 같은 부모를 갖는다고 정의한다면 P[1] = P[2] = P[3] 이며 1 또는 2 또는 3의 값을 가집니다. 편의상 부모 노드의 번호가 작은쪽으로.. 2020. 8. 9. 이전 1 다음
