알고리즘
Union Find - 유니온 파인드
정의 그래프 알고리즘의 일종 상호 배타적 집합, Disjoint-set을 표현하기 위해 사용 서로 중복되지 않는 부분 집합들 포함 관계 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘 두 가지 연산 Find 노드 X가 속해있는 집합 반환 Union (합집합) 노드 X가 포함된 집합과 노드 Y가 포함된 집합을 합치는 연산 접근 Union → 그래프의 노드연결 연결 정보가 주어질 경우 집합을 합쳐야 하는 경우 Find → 어느 그래프에 속해있는지 연결 정보를 가지고 어떤 집합에 속해있는지 찾을 때(반대로 속해있지 않은 경우도) 구현 트리 형태 사용 “부모 포인터 표현” 사용 각 노드에 대해 그 노드의 부모에 대한 포인터만 저장 ..