🐳Dev/Algorithm

[μ•Œκ³ λ¦¬μ¦˜] 03. Union-Find

fortune.00 2021. 11. 22. 16:55

Pair-wise Disjoint Sets

Disjoint Set

: λ‹€λ₯Έ μ§‘ν•©κ³Ό μ€‘λ³΅λ˜λŠ” μ›μ†Œκ°€ μ—†λŠ” 집합을 λ‹€λ£¨λŠ” 자료ꡬ쑰, 즉 ν•˜λ‚˜μ˜ μ›μ†ŒλŠ” λ°˜λ“œμ‹œ ν•˜λ‚˜μ˜ μ§‘ν•©μ—λ§Œ μ†ν•œλ‹€. 이λ₯Ό μƒν˜Έ 배타적이라고 ν•œλ‹€.

 

κΈ°λ³Έ μ—°μ‚°

  1. μ΄ˆκΈ°ν™” : 각각의 μ›μ†Œλ₯Ό ν•˜λ‚˜μ˜ μ§‘ν•©μœΌλ‘œ ν‘œν˜„.(μ΄ˆκΈ°μ—λŠ” μ›μ†Œμ˜ 개수만큼 집합이 쑴재)
  2. find(i) : μ›μ†Œ iκ°€ μ†ν•΄μžˆλŠ” 집합을 μ°Ύμ•„, λ°˜ν™˜ν•œλ‹€.
  3. 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