Coding Test(Union-Find, Disjoint-set)

유니온 파인드(Union-Find)

Disjoint-set(서로소 집합, 분리 집합) 이라고도 하며 순수히 노드 간의 연결 관계를 파악할 때 유용하게 사용

무방향 그래프 내에서의 사이클을 판별할 때 사용(서로의 Root Node가 같다면 사이클 발생)

방향 그래프에서 사이클을 판별할 땐 DFS(DFS타다가 자기자신으로 돌아오면 사이클 발생)

0) Make

- 간선이 아직 연결되어있지 않은 그래프에서 모든 값이 자기 자신을 가르키게한다

= > 자기 자신이 부모노드가된다

for(int i=1;i<=N;i++)
    group[i]=i;//자기 자신 넣기

1) Union (서로 다른 노드(집합, 연결관계)를 합쳐서 서로 연결되게 하는 연산)

def union(a, b):
    a = find(a)
    b = find(b)

    # 작은 루트 노드를 기준으로 합침
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

public static void union(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if(rootA < rootB)	//오름차순 
        group[rootB] = rootA;
    else
        group[rootA] = rootB;
}

- 합칠 노드의 루트를 찾은다음 부모노드가 더 작은 애한테 나의 부모는 이제 얘다. 라고 명시해주는 것임

2) Find (Root Node를 찾는 연산)

- 부모 노드를 찾는 것이 아닌 루트 노드를 찾는 것

- parent는 루트 노드를 담는 리스트가 아닌 부모 노드를 담는 리스트이지만

 루트 노드의 정보를 담아서 경로 압축 최적화를 하면 효율적으로 동작

def find(target):
    '''
    #시간복잡도 O(V), 모든 노드를 다 확이하게 되어 비효율적임
    # 여기서는 루트 노드 를 찾아서 return만 시켜준건데
    if parent[target] != target:
        return find(parent[target])
    return target
    '''

    if parent[target] != target:
        # 경로 압축 최적화
        parent[target] = find(parent[target])
    return parent[target]

public static int find(int x) {
		if(group[x]==x)
			return x;
		else
			return find(group[x]);
	}
    
public static int find(int x) {
    if(group[x] != x)
        group[x] = find(group[x]);
    return group[x];
}

 

단순 재귀 호출(주석 부분)

* 경로 압축을 해준다고 해서 parent의 값들이 루트를 가르키는건 아님

* find(target)을 해주니까 루트를 가르킴

경로 압축 최적화를 적용

 

<Code>

# find 연산
def find(target):
    if parent[target] != target:
        # 경로 압축 최적화
        parent[target] = find(parent[target])
    return parent[target]
    
# union 연산
def union(a, b):
    a = find(a)
    b = find(b)

    # 작은 루트 노드를 기준으로 합침
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

parent = [0, 1, 2, 3, 4, 5]

print(find(1), find(2), find(3), find(4), find(5))
print(parent)

union(4, 5)
union(3, 4)
union(2, 3)
union(1, 2)

print(find(1), find(2), find(3), find(4), find(5))
print(parent)