유니온 파인드
상호 배타적 집합이라고도 한다.
2가지 연산으로 이루어져 있다.
1. Find: x가 어떤 집합에 포함되어 있는지 찾는 연산
2. Union: x와 y가 퐇마되어 있는 집합을 합치는 연산
- 구현은 트리를 이용해서 한다.
- parent[i] = i 의 parent 가 저장되어 있음
* parent[] 배열을 각자 자기 번호로 초기화 하는 것에 주의
** find 연산에서 결과를 가지고 있다가 저장하고 반환하는 것에 주의
*** 이 union, find 연산은 MST의 크루스칼 알고리즘에 사용된다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1005 ACM Craft (0) | 2017.07.20 |
---|---|
[백준][트리] 1197 최소 스패닝 트리(크루스칼 알고리즘) (0) | 2017.07.06 |
[백준][그래프] 2623 음악프로그램 (0) | 2017.07.04 |
[백준][위상정렬] 2056 작업 DAG (0) | 2017.06.27 |
[백준][다이나믹] 1890 점프 (0) | 2017.06.26 |