유니온 파인드 알고리즘, python

유니온 파인드 알고리즘이란?

 

유니온 파인드 알고리즘이란, 두 집합을 하나로 합치고(union) 두 원소가 같은 집합에 속해있는지 확인하는(find) 알고리즘이다.

 

유니온 파인드를 구현하기 위해서는 부모노드의 번호를 저장할 parents배열과, 트리의 레벨을 저장할 level 배열이 필요하다.

parents배열의 초기값은 자기 자신의 번호이고, level은 0이다.

 

선택된 노드의 루트노드를 찾는 find 함수와, 두 원소를 하나로 합치는 union 함수가 필요하다.

find함수는 재귀를 통해 자신이 속한 트리의  루트노드의 번호를 반환한다.

union함수는 합칠 두 원소의 루트노드의 번호를 찾고, 레벨이 더 깊은 트리에 작은 트리를 합친다.

 

 

 

 

 

 

union 과정

 

예를 들어 5개의 원소가 있다.

 

다음과 같은 순서로 합치려고 한다.

A	B
0	1
0	2
3	4
1	4

 

 

 

 

 

 

	0	1	2	3	4
parents	0	1	2	3	4
level	0	0	0	0	0

 

먼저 parents와 level의 초기값을 설정한다.

 

 

 

 

 

 

0과 1을 합친다.

	0	1	2	3	4
parents	0	1->0	2	3	4
level	0->1	0	0	0	0

 

0의 루트노드는 0이고, 1의 루트노드는 1이다.

0이 루트노드인 트리의 레벨은 0이고, 1이 루트노드인 트리의 레벨도 0이다.

합치려는 두 트리의 높이가 같으므로, 0의 트리의 레벨을 1 늘리고, 1이 루트노드인 트리를 0 밑에 붙여준다.

여기서 1의 루트노드는 0으로 바뀌게된다.

 

 

 

 

 

 

 

0과 2를 합친다.

	0	1	2	3	4
parents	0	0	2->0	3	4
level	1	0	0	0	0

 

0의 루트노드는 0이고, 2의 루트노드는 2이다.

0이 루트노드인 트리의 레벨은 1이고, 2가 루트노드인 트리의 레벨은 0이다.

0의 깊이가 더 깊으므로 2를 0 밑에 붙여준다.

2의 루트노드는 0으로 바뀌게 된다.

 

 

 

 

 

 

 

3과 4를 합친다.

	0	1	2	3	4
parents	0	0	0	3	4->3
level	1	0	0	0->1	0

 

3의 루트노드는 3이고, 4의 루트노드는 4이다.

3이 루트노드인 트리의 레벨은 0이고, 4가 루트노드인 트리의 레벨도 0이다.

합치려는 두 트리의 높이가 같으므로, 3의 트리의 레벨을 1 늘리고, 4가 루트노드인 트리를 3 밑에 붙여준다.

4의 루트노드는 3으로 바뀌게 된다.

 

 

 

 

 

 

 

 

1과 4를 합친다.

	0	1	2	3	4
parents	0	0	0	3->0	3
level	1->2	0	0	1	0

 

1의 루트노드는 0이고, 4의 루트노드는 3이다.

0이 루트노드인 트리의 레벨은 1이고, 3이 루트노드인 트리의 레벨도 1이다.

합치려는 두 트리의 높이가 같으므로, 0의 트리의 레벨을 1 늘리고, 3이 루트노드인 트리를 0 밑에 붙여준다.

3의 루트노드는 0으로 바뀌게 된다.

 

 

 

 

 

 

모든 union을 하고 나면 다음과 같이 나오게 된다.

	0	1	2	3	4
parents	0	0	0	0	3
level	2	0	0	1	0

 

 

 

 

 

 

 

이제 두 원소가 같은 집합에 속하는지를 알고 싶으면 find함수를 통해 해당노드의 루트노드가 같은지를 판별하면 된다.

 

 

4번 노드의 루트노드는 find함수에서 재귀를 통해 루트노드까지 거슬러 올라가며 값을 최신화 해준다. 4번노드의 루트노드는 0번이다.

1번 노드도 마찬가지로 루트노드는 0번이다.

두 노드의 루트노드가 같으므로 같은 집합에 속해 있다.

 

 

 

 

 

 

python 구현

 

유니온 파인드를 구현하기 위해서는 parents배열과 level배열만 구현하면 된다.

parents = [x for x in range(n)]
level = [0]*n

 

먼저 parents노드는 자신의 노드번호로, level은 0으로 초기화를 해준다.

 

 

 

def find(x):
    if parents[x] != x:
        parents[x] = find(parents[x])
    return parents[x]

 

find함수는 root의 노드가 자기 자신인 경우(자식노드가 아닌 경우) 자신의 부모노드로 거슬러 올라가며 루트노드를 찾는다.

이때 root [x] = find(root [x]) 를 통해 루트노드를 찾는 과정에서 최신화되지 않은 노드들의 루트노드를 업데이트해준다.

이 과정을 경로 압축이라고 한다.

 

 

 

def union(x,y):
    # 각각의 루트노드를 찾는다
    x = find(x)
    y = find(y)

    # x를 루트노드로 한 트리의 깊이가 깊으면 x트리 밑에 y트리를 붙여준다.
    # y의 루트노드를 x로 바꿔준다.
    if level[x]>level[y]:
        parents[y] = x

    # y를 루트노드로 한 트리의 깊이가 깊으면 y트리 밑에 x트리를 붙여준다.
    # x의 루트노드를 y로 바꿔준다.    
    elif level[x]<level[y]:
        parents[x] = y

    # 두 트리의 높이가 같다면 x 트리의높이를 1늘려주고 x트리 밑에 y트리를 붙인다.
    else:
        level[x] += 1
        parents[y] = x

 

합치려는 두 원소 x, y의 루트노드를 찾고, 깊이를 비교해 레벨이 더 깊은 쪽에 붙이고 루트노드를 업데이트해준다.

만약 두 트리의 레벨이 같다면, 한쪽 트리의 레벨을 올리고 그 밑에 붙여준다.

 

 

 

 

 

 

유니온 파인드를 사용하여 해결할 수 있는 문제

 

[백준] 17471 게리맨더링

[백준] 17471 게리맨더링

 

[백준] 10775 공항

[백준] 10775 공항