[μκ³ λ¦¬μ¦] 03. Union-Find
Pair-wise Disjoint Sets
Disjoint Set
: λ€λ₯Έ μ§ν©κ³Ό μ€λ³΅λλ μμκ° μλ μ§ν©μ λ€λ£¨λ μλ£κ΅¬μ‘°, μ¦ νλμ μμλ λ°λμ νλμ μ§ν©μλ§ μνλ€. μ΄λ₯Ό μνΈ λ°°νμ μ΄λΌκ³ νλ€.
κΈ°λ³Έ μ°μ°
- μ΄κΈ°ν : κ°κ°μ μμλ₯Ό νλμ μ§ν©μΌλ‘ νν.(μ΄κΈ°μλ μμμ κ°μλ§νΌ μ§ν©μ΄ μ‘΄μ¬)
- find(i) : μμ iκ° μν΄μλ μ§ν©μ μ°Ύμ, λ°ννλ€.
- union(s1, s2) : κ²ΉμΉλ μμκ° μλ λ μ§ν©μ νλλ‘ ν©νλ€.
A = {0, 1}, B = {2, 3, 4}, C = {5, 6}
union(A, C) == {0, 1, 5, 6}
find(3) == B
Disjoint Set νν
- νΈλ¦¬κ΅¬μ‘°λ₯Ό ν΅ν, 1μ°¨μ λ°°μ΄λ‘ νν
- κ° μμλ λΆλͺ¨μμλ₯Ό κ°λ₯΄ν€λ©°, 루νΈλ -1μ κ°μΌλ‘ κ°μ§.
- 루νΈμ λ°°μ΄μ μΈλ±μ€λ μ§ν©μ μ΄λ¦μΌλ‘ μ¬μ©.
Union Find Algorithm
Union
Weighting Rule
: νΈλ¦¬μ ν¬κΈ°λ₯Ό μ΄μ©ν΄, λμ΄λ₯Ό μ΅μν νλ λ°©λ²μ΄λ€
: νΈλ¦¬μ ν¬κΈ°κ° ν° μͺ½μ΄ νΈλ¦¬μ λμ΄κ° ν΄κ²μ΄λΌκ³ κ°μ νμ λ, (μμΈ μ‘΄μ¬) νΈλ¦¬μ ν¬κΈ°κ° ν° μͺ½μ νΈλ¦¬μ ν¬κΈ°κ° μμ νΈλ¦¬λ₯Ό λΆμ¬ λμ΄λ₯Ό μ΅μννλ€
: νΈλ¦¬μ ν¬κΈ°λ₯Ό 루νΈμ μμ κ°μΌλ‘ μ μ₯νλ€
public void union(int a, int b){
a = find(a);
b = find(b);
if(a == b) return;
if(tree[a] < tree[b]) {//κ°μ΄ μλ€ == ν° νΈλ¦¬λ₯Ό μλ―Έ
tree[a] += tree[b];
tree[b] = a;
}
else{
tree[b] += tree[a];
tree[a] = b;
}
}
Find
Collapsing Rule
: νΈλ¦¬μ λ
Έλλ₯Ό μ΅λν λμ§ μκ² μ μ§νλ€λ©΄, findμ ν¨μ¨μ μ΄λ€
: λ°λΌμ findλ₯Ό νλ©΄μ κ²½λ‘μμ λ
Έλλ€μ 루νΈμ μμμΌλ‘ λ§λ λ€
public int find(int a){
if(tree[a] < 0) return a; //root
return tree[a] = find(tree[a]);
//λΆλͺ¨μμ μμμΌλ‘ λ΄λ €κ°λ©΄μ, rootμ μ°κ²°μν΄.
}
GitHub - Sinyoung3016/sophomore-lecture: 2020λ μΆ©λ¨λνκ΅ μ»΄ν¨ν°μ΅ν©νλΆ 2νλ λμ κ³Όμ λ€μ λͺ¨μλͺ¨μ
2020λ μΆ©λ¨λνκ΅ μ»΄ν¨ν°μ΅ν©νλΆ 2νλ λμ κ³Όμ λ€μ λͺ¨μλͺ¨μ. Contribute to Sinyoung3016/sophomore-lecture development by creating an account on GitHub.
github.com