Union Find와 경로 압축

간단하게 union find 알고리즘과 경로 압축 알고리즘에 대해서 적어본다.

Union Find(disjoint set)

disjoint Set이라고도 하며 트리나 그래프의 연결 유무를 확인하기 위한 알고리즘이다.

find 와 union 의 2가지 메서드를 가진다. find 는 트리의 루트를 확인하며, union는 루트가 다른 두 트리의 루트를 병합하기 위한 메서드이다.

find()- O(n)

union()-O(n)

최악의 경우 linear tree에서 두 경우 모두 O(n) 시간복잡도를 가진다. 높이가 분산되지 않고 그대로 선형으로 높이가 계속 증가하는 경우가 되며, 이 경우 find가 O(n), union은 find를 2회 수행하므로 마찬가지로 O(n)이다.

이를 해결하기 위한 2가지 방법을 사용한다. 첫번째는 Union by rank, 두번째는 find 와 함께 경로를 압축하는 path compression 이다.

Union by Rank union() 함수 호출 시, 서로 다른 루트를 가진 트리의 rank가 다르다면 rank가 높은 트리의 루트에 rank가 낮은 트리가 병합되록 하고, rank 가 같을 시에 rank+=1 을 해주는 방식, 즉, 트리의 높이를 분산시키기 위함

class UnionFind(size:Int){
    val root:IntArray by lazy { IntArray(size){it} }
    val rank:IntArray by lazy { IntArray(size){1} }
	  
    fun union(x:Int, y:Int){
        val rootX = find(x)
        val rootY = find(y)
        if(rootX!=rootY){
            when{
                rank[rootX]>rank[rootY] -> root[rootY] = rootX
                rank[rootX]<rank[rootY]-> root[rootX]= rootY
                else->{
                    root[rootY]= rootX
                    rank[rootX]+=1
                }
            }
        }

    }
}

기존 find(): O(n)

fun find(x:Int):Int{
	while(x!=root[x]) x= root[x]
	return x
}

문제점: 트리가 선형일경우(높이가 분산되지 않을 경우) O(n)이 강제됨

Path Compression :O(log(n)) 최선 O(1), 최악 O(n) → find 수행 시에 union rank 의 역할과 마찬가지로 트리의 높이를 분산해줌.

fun find(x:Int):Int{
	if(x==root[x])return x
	root[x] = find(root[x])
	return root[x]
}

최종

class UnionFind(size:Int){
    val root:IntArray by lazy { IntArray(size){it} }
    val rank:IntArray by lazy { IntArray(size){1} }
	  
    fun union(x:Int, y:Int){
        val rootX = find(x)
        val rootY = find(y)
        if(rootX!=rootY){
            when{
                rank[rootX]>rank[rootY] -> root[rootY] = rootX
                rank[rootX]<rank[rootY]-> root[rootX]= rootY
                else->{
                    root[rootY]= rootX
                    rank[rootX]+=1
                }
            }
        }

    }
	fun find(x:Int):Int{
      if(x==root[x]) return x
      root[x] = find(root[x])
      return root[x]
  	}
}