백준/분리 집합 (Disjoint Set, Union - Find)
-
유니온 파인드 (Union - Find) 알고리즘백준/분리 집합 (Disjoint Set, Union - Find) 2022. 6. 19. 21:56
1. 유니온 파인드 알고리즘 유니온 파인드 알고리즘에 대해 알아본다. 여러 노드 존재 시, 임의의 두 개 노드가 서로 같은 그래프에 속하는지 판별한다. 1. 배열, 메소드 설명 일단 이 알고리즘에 사용되는 배열, 메소드를 설명하겠다. 1) parent[i] 배열 각 노드 i가 어떤 부모에 포함되는지 나타낸다. 노드가 6개 있을 때 처음에는 모두 연결되지 않는 상태이다. 자기 자신만을 집합의 원소로 가지고 있다. 그래서 다음과 같다. 2) find 메소드 find(a) : a가 어느 집합에 포함되어 있는지 찾는다. 3) union 메소드 union(a,b) : a와 b가 포함되어 있는 집합을 합친다. 2. union 실행 union(1,2) 를 실행해보자. 일반적으로 더 작은 값 쪽으로 합친다고 한다. 그..