정의
- 그래프 알고리즘의 일종
- 상호 배타적 집합, Disjoint-set을 표현하기 위해 사용
- 서로 중복되지 않는 부분 집합들
- 포함 관계
- 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘
- 두 가지 연산
- Find
- 노드 X가 속해있는 집합 반환
- Union (합집합)
- 노드 X가 포함된 집합과 노드 Y가 포함된 집합을 합치는 연산
접근
- Union → 그래프의 노드연결
- 연결 정보가 주어질 경우 집합을 합쳐야 하는 경우
- Find → 어느 그래프에 속해있는지
- 연결 정보를 가지고 어떤 집합에 속해있는지 찾을 때(반대로 속해있지 않은 경우도)
구현
- 트리 형태 사용
- “부모 포인터 표현” 사용
- 각 노드에 대해 그 노드의 부모에 대한 포인터만 저장
- 같은 부모 → 같은 집합
- 1차원 배열로 구현 가능
- -1은 부모가 없다는 뜻
- 배열의 인덱스를 부모에 대한 포인터로 사용
예
- -1은 부모가 없거나 자신이 부모인 경우
- -1로 초기화된 배열
| A | B | C | D | E | F |
| -1 | -1 | -1 | -1 | -1 | -1 |
- Union(A, B)
| A | B | C | D | E | F |
| -1 | 0 | -1 | -1 | -1 | -1 |
- Union(A, C)
| A | B | C | D | E | F |
| -1 | 0 | 0 | -1 | -1 | -1 |
- Union(B, C)
- 둘이 부모가 같으므로 아무 일도 일어나지 않음 -> 사이클이 생기지 않음
| A | B | C | D | E | F |
| 0 | 0 | 0 | -1 | -1 | -1 |
- Union(B, D), Union(E, F)
| A | B | C | D | E | F |
| -1 | 0 | 0 | 1 | -1 | 4 |
- Union(A, F)
| A | B | C | D | E | F |
| -1 | 0 | 0 | 1 | 0 | 4 |
코드
public int[] parents = new int[n];
public void union(int a, int b) {
int root1 = find(a);
int root2 = find(b);
if (root1 != root2) {
if (root2 > root1)
parents[root2] = root1;
else
parents[root1] = root2;
}
}
public int find(int a) {
if(parents[a] == -1)
return a;
return find(parents[a]);
}연습문제
'알고리즘' 카테고리의 다른 글
| [LeetCode] 162. Find Peak Element (0) | 2022.07.28 |
|---|---|
| [LeetCode] 153. Find Minimum in Rotated Sorted Array (0) | 2022.07.26 |
| [LeetCode] 33. Search in Rotated Sorted Array (0) | 2022.07.25 |
| Dijkstra - 다익스트라 (0) | 2022.05.30 |
| [LeetCode] 191. Number of 1 Bits (0) | 2022.05.25 |
정의
- 그래프 알고리즘의 일종
- 상호 배타적 집합, Disjoint-set을 표현하기 위해 사용
- 서로 중복되지 않는 부분 집합들
- 포함 관계
- 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘
- 두 가지 연산
- Find
- 노드 X가 속해있는 집합 반환
- Union (합집합)
- 노드 X가 포함된 집합과 노드 Y가 포함된 집합을 합치는 연산
접근
- Union → 그래프의 노드연결
- 연결 정보가 주어질 경우 집합을 합쳐야 하는 경우
- Find → 어느 그래프에 속해있는지
- 연결 정보를 가지고 어떤 집합에 속해있는지 찾을 때(반대로 속해있지 않은 경우도)
구현
- 트리 형태 사용
- “부모 포인터 표현” 사용
- 각 노드에 대해 그 노드의 부모에 대한 포인터만 저장
- 같은 부모 → 같은 집합
- 1차원 배열로 구현 가능
- -1은 부모가 없다는 뜻
- 배열의 인덱스를 부모에 대한 포인터로 사용
예
- -1은 부모가 없거나 자신이 부모인 경우
- -1로 초기화된 배열
| A | B | C | D | E | F |
| -1 | -1 | -1 | -1 | -1 | -1 |
- Union(A, B)
| A | B | C | D | E | F |
| -1 | 0 | -1 | -1 | -1 | -1 |
- Union(A, C)
| A | B | C | D | E | F |
| -1 | 0 | 0 | -1 | -1 | -1 |
- Union(B, C)
- 둘이 부모가 같으므로 아무 일도 일어나지 않음 -> 사이클이 생기지 않음
| A | B | C | D | E | F |
| 0 | 0 | 0 | -1 | -1 | -1 |
- Union(B, D), Union(E, F)
| A | B | C | D | E | F |
| -1 | 0 | 0 | 1 | -1 | 4 |
- Union(A, F)
| A | B | C | D | E | F |
| -1 | 0 | 0 | 1 | 0 | 4 |
코드
public int[] parents = new int[n];
public void union(int a, int b) {
int root1 = find(a);
int root2 = find(b);
if (root1 != root2) {
if (root2 > root1)
parents[root2] = root1;
else
parents[root1] = root2;
}
}
public int find(int a) {
if(parents[a] == -1)
return a;
return find(parents[a]);
}연습문제
'알고리즘' 카테고리의 다른 글
| [LeetCode] 162. Find Peak Element (0) | 2022.07.28 |
|---|---|
| [LeetCode] 153. Find Minimum in Rotated Sorted Array (0) | 2022.07.26 |
| [LeetCode] 33. Search in Rotated Sorted Array (0) | 2022.07.25 |
| Dijkstra - 다익스트라 (0) | 2022.05.30 |
| [LeetCode] 191. Number of 1 Bits (0) | 2022.05.25 |
