Union Find 알고리즘

Union Find 알고리즘이란?

합집합을 찾는 알고리즘 - 원소들이 연결 되었는지 여부를 찾을 때 유용

배열에 해당 원소가 속한 집합의 루트 원소를 입력한다.
(일반적으로 적은 숫자 또는 사전 순서로 빠른 문자)

같은 루트를 가지는 경우 같은 집합에 속해 있다는 의미

예시) 원소가 1, 2, 3, 4일 경우

1	2	3	4
1	2	3	4

1, 2, 3, 4 각 원소는 각기 다른 집합에 속해 있음


1, 2번 원소의 집합을 합칠 경우

1	2	3	4
1	1	3	4

1번 원소가 속한 집합과 2번 원소가 속한 집합을 묶는다는 의미로 2번의 값을 1로 변경
(루트가 1인 집합에 속함)

2번, 4번 원소의 집합을 합칠 경우

1	2	3	4
1	1	3	1

2번 원소가 속한 집합과 4번 원소가 속한 집합을 묶음 (4번도 1번이 루트인 집합에 넣음)

위 로직을 구현하기 위해 필요한 함수

1. find(x) 함수
   원소 x가 속한 집합의 루트 원소를 반환하는 함수.

fun find(x: Int): Int{
	if(x == parent[x])
    	return x
    else{
    	val p = find(parent[x])
        parent[x] = p // 거슬러 올라가며 루트 원소로 대입하여 x 인덱스의 값이 집합의 루트가 되도록
        return parent[x]
    }
}

x가 집합의 루트 원소이면 x를 그대로 반환하고 루트 원소가 아닐 경우 재귀적으로 해당 원소가 속한 집합의 루트 원소를 거슬러 올라가며 루트 원소를 반환함.

이 부분에서 parent[x] = p 코드가 왜 필요한지는 아래 union 함수에서 추가로 설명하겠다.

2. union(x, y) 함수
   x가 속한 집합과 y가 속한 집합을 합치는 함수.

fun union(x: Int, y: Int){
	val rootX = find(x)
    val rootY = find(y)
    
    parent[rootY] = rootX
}

원소 x의 루트와 원소 y의 루트를 찾아 rootY의 값을 rootX의 값으로 바꾸어 주며 x의 집합에 y를 포함시킴.

1	2	3	4
1	2	3	4

위 과정을 나타내보면

1. 1번과 2번을 union 함수로 연결

1	2	3	4
1	1	3	4

2. 2번과 4번을 union 함수로 연결

1	2	3	4
1	1	3	1

하지만 이런 경우도 존재할 수 있다.

1. 2번과 4번을 union 함수로 연결

1	2	3	4
1	2	3	2

2. 1번과 2번을 union 함수로 연결

1	2	3	4
1	1	3	2

위의 4번 원소의 경우처럼 해당 집합의 루트 원소가 아닌 중간다리 원소(2번)가 입력되는 경우가 존재할 수 있다.

위 구조에서 4번 원소에 대해 find를 호출할 경우 1 - 2 - 4 연결구조를 거슬러 올라가게 되고, 위에선 3개의 원소지만 만약 경로가 매우 길어질 경우 비효율적으로 작동할 수 있다.

이 경우를 방지하기 위해 find함수에서 parent[x] = p 코드를 추가한 것이다.

바로 위 케이스를 예를 들면, 4번 원소에서 find를 호출하면 (union 함수 내의 find 포함) 집합의 루트인 1번을 구하고 이를 4번 위치에 넣어줌으로써 1 - 2 - 4로 연결된 구조를 1 - (2, 4) 구조로 단순화할 수 있다.