반응형
인프런 알고리즘 강의 18강에 대한 리뷰다.
union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다.
find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.
union-find 자료구조는 다른말로 서로소 집합(Disjoint Sets) 자료구조라고도 불린다.
* 서로소 집합은 공통 원소가 없는 두 집합을 의미한다.
union-find는 보통 트리 자료구조를 이용하여 집합을 표현한다.
union 연산의 알고리즘은 다음과 같다.
- union 연산을 확인하여 서로 연결된 두 노드 A, B를 확인한다.
- A와 B의 루트 노드를 찾는다
- 재귀적으로 부모 노드를 찾아 루트 노드를 찾는다. (A`, B`)
- B`가 A`를 부모 노드로 설정하게 한다. (B`가 A`를 가리키도록 한다.)
- (대개 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 한다.)
- 모든 union 연산을 처리할 때까지 1의 과정을 반복한다.
** C++
#include <stdio.h>
// 재귀적으로 부모 노드를 찾음
int getParent(int parent[], int x) {
if (parent[x] == x) return x;
return parent[x] = getParent(parent, parent[x]);
}
// 두 부모 노드를 합치는 함수
int unionParent(int parent[], int a, int b) {
a = getParent(parent, a);
b = getParent(parent, b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
// 같은 부모인지 확인하는 함수
int findParent(int parent[], int a, int b) {
a = getParent(parent, a);
b = getParent(parent, b);
if (a == b) return 1;
return 0;
}
int main(void) {
int parent[11]; // 부모 테이블 초기화
for (int i = 1; i <= 10; i++) {
parent[i] = i; // 자기 자신을 부모로 가지도록 설정
}
unionParent(parent, 1, 2);
unionParent(parent, 2, 3);
unionParent(parent, 3, 4);
unionParent(parent, 5, 6);
unionParent(parent, 6, 7);
unionParent(parent, 7, 8);
printf("1과 5는연결되어 있나요? %d\n", findParent(parent, 1, 5));
unionParent(parent, 1, 6); // 1 - 5, 6, 7 / 2 - 8
printf("1과 5는연결되어 있나요? %d\n", findParent(parent, 1, 5));
}
** Javascript
// 재귀적으로 부모 노드를 찾음
function getParent(parent, x) {
if (parent[x] == x) return x;
return parent[x] = getParent(parent, parent[x]);
}
// 두 부모 노드를 합치는 함수
function unionParent(parent, a, b) {
a = getParent(parent, a);
b = getParent(parent, b);
if (a < b) parent[b] = a
else parent[a] = b;
}
// 같은 부모인지 확인하는 함수
function findParent(parent, a, b) {
a = getParent(parent, a);
b = getParent(parent, b);
if (a == b) return "true";
return "false";
}
function main() {
let parent = [0];
for (let i = 1; i <= 10; i++) {
parent.push(i);
}
unionParent(parent, 1, 2);
unionParent(parent, 2, 3);
unionParent(parent, 3, 4);
unionParent(parent, 5, 6);
unionParent(parent, 6, 7);
unionParent(parent, 7, 8);
console.log(`1과 5는연결되어 있나요? ${findParent(parent, 1, 5)}`);
unionParent(parent, 1, 6); // 1 - 5, 6, 7 / 2 - 8
console.log(`1과 5는연결되어 있나요? ${findParent(parent, 1, 5)}`);
}
main();
** Java
public class Main
{
private static int getParent(int[] parent, int x) {
if (parent[x] == x) return x;
return parent[x] = getParent(parent, parent[x]);
}
private static void unionParent(int[] parent, int a, int b) {
a = getParent(parent, a);
b = getParent(parent, b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
private static String findParent(int[] parent, int a, int b) {
a = getParent(parent, a);
b = getParent(parent, b);
if (a == b) return "true";
return "false";
}
public static void main(String[] args) {
int[] parent = new int[11];
for (int i = 1; i <= 10; i++) {
parent[i] = i;
}
unionParent(parent, 1, 2);
unionParent(parent, 2, 3);
unionParent(parent, 3, 4);
unionParent(parent, 5, 6);
unionParent(parent, 6, 7);
unionParent(parent, 7, 8);
System.out.printf("1과 5는연결되어 있나요? %s\n", findParent(parent, 1, 5));
unionParent(parent, 1, 6); // 1 - 5, 6, 7 / 2 - 8
System.out.printf("1과 5는연결되어 있나요? %s\n", findParent(parent, 1, 5));
}
}
** Python
def getParent(parent, x):
return parent[x] if parent[x] == x else getParent(parent, parent[x])
def unionParent(parent, a, b):
a = getParent(parent, a)
b = getParent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
def findParent(parent, a, b):
a = getParent(parent, a)
b = getParent(parent, b)
return "true" if a == b else "false"
def main() :
parent = [0]
for i in range(1, 11):
parent.append(i)
unionParent(parent, 1, 2)
unionParent(parent, 2, 3)
unionParent(parent, 3, 4)
unionParent(parent, 5, 6)
unionParent(parent, 6, 7)
unionParent(parent, 7, 8)
print(f'1과 5는 연결되어 있나요? {findParent(parent, 1, 5)}')
# unionParent(parent, 2, 8)
print(f'1과 5는 연결되어 있나요? {findParent(parent, 1, 5)}')
if __name__ == "__main__":
# execute only if run as a script
main()
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
def has_same_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
return "true" if a == b else "false"
def main() :
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화
for i in range(1, v + 1):
parent[i] = i # 부모 노드를 자기 자신으로 초기화
# union 연산 수행
for i in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
# 각 원소가 속한 집합 출력
print("각 원소가 속한 집합: ")
for i in range(1, v + 1):
print(find_parent(parent, i))
print()
# 부모 테이블 내용 출력
print("부모테이블: ")
for i in range(1, v + 1):
print(parent[i])
if __name__ == "__main__":
# execute only if run as a script
main()
반응형
'Algorithm > 알고리즘 스터디(2021.07)' 카테고리의 다른 글
[Algorithm] 이진 트리의 구현과 순회 알고리즘 (0) | 2021.09.26 |
---|---|
[Algorithm] Kruskal Algorithm (크루스칼 알고리즘) (0) | 2021.09.12 |
[Algorithm] DFS (깊이 우선 탐색) (0) | 2021.09.02 |
[Algorithm] BFS (너비우선탐색) (0) | 2021.09.02 |
[Algorithm] Queue (큐) (0) | 2021.08.25 |