보스찾기 union find 알고리즘

오랜만에 문제풀다 하나씩 

 

오늘은 union find disjoint set 알고리즘을 공부할 차례 

 

보스가 -1이고 보스랑 연결되어 있는 조직원 찾고, 

그 조직원과 보스가 묶인 부분집합이 몇 개있는지 찾는 문제다 

 

https://brownbears.tistory.com/460

[Python] union find (disjoint-set) 알고리즘

 

 

union find(disjoint-set)의 핵심은 아래 3가지.

1. 초기화 : N 개의 원소가 각각의 집합에 포함되어 있도록 초기화

2. Union 연산 : 두 원소 a, b 가 주어질 때, 이들이 속한 두 집합을 하나로 합침

3. Find 연산 : 어떤 원소 a 가 주어질 때, 이 원소가 속한 집합을 반환

 

Union-Find의 사용 예시
전체 집합이 있을 때 구성 원소들이 겹치지 않도록 분할(아래 참고*)하는 데 자주 사용된다.

Kruskal MST 알고리즘에서 새로 추가할 간선의 양끝 정점이 같은 집합에 속해 있는지(사이클 형성 여부 확인)에 대해 검사하는 경우
초기에 {0}, {1}, {2}, … {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려는 경우
집합의 표현-백준1717번
어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 가입한 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하는 경우
친구 네트워크-백준4195번

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

기본적인 find, union 알고리즘 함수 

# https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html 를 c->python화

root = (x for x in range(MAX_SIZE)

# find()는 재귀다
def find(x):
	if root[x] == x:
    	return x
    else:
    	return find(root[x])

def union(x, y):
	x = find(x)
    y = find(y)
    
    # 자식 인덱스 값을 부모로 업데이트해준다 
    root[y] = x

 

경로 압축 알고리즘 

root = [x for x in range(100)]

def find(x):
  if root[x] == x:
  	return x
  else:
  	return root[x] = find(root[x])
    # find를 수행하면서 만난 모든 부모 노드를 루트 노드로 바꿔준다