[Algorithm] 유니온 파인드(Union-Find) 알고리즘
유니온 파인드(Union-Find) 알고리즘 분리집합 (서로소 집합, Disjoint Set)의 합집합(Union)과 같은 집합에 속하는지 여부(Find) 를 확인하는 알고리즘. 예시는 정수들의 집합으로하겠다. 1~9 까지 정수 9개가 각각 하나의 집합이라고 하자. {1}, {2}, {3} ,{4}, {5}, {6}, {7}, {8}, {9} 각 정수가 하나의 노드라고 하고, 그래프라고 한다면 초기 상태는 각각 부모노드가 자기 자신인 구조로 설정한다. 이것을 프로그래밍적으로 표현한다면 2차원 배열로 다음과 같이 표현할 수 있다. Node 1 2 3 4 5 6 7 8 9 Parent 1 2 3 4 5 6 7 9 9 여기서 집합 {1} 과 {2} 를 합친다고 하면 다음과 같이 공통의 부모를 두도록 하면 된다..
2021. 9. 2.