유니온 파인드, disjoint set (4195 친구 네트워크)

유니온 파인드

말 그대로 집합,공동체를 찾는다는 것이다.

집합으로 묶어서 풀면 좋은 문제를 풀 때 효율적으로 풀기좋다.

특히 집합끼리 묶는것을 쉽게 만들어 준다.

모든 원소들을 자기 자신을 부모노드로 초기화 한다.

집합을 합치는 것은 부모노드를 같게 만들어줌으로써 집합을 만들 수 있다.

같은집합에 속해있는것은 find를 통해 부모노드를 찾는 함수를 활용하여 같은 부모노드를 가르키면

같은 집합,아니면 다른 집합에 포함되있는 것이다.

 

유니온 파인드에는 3가지 과정이 있다.

1.각자 자신으로 부모노드를 초기화한다.

2.find(부모노드 찾기)

def find(v):
    if parent[v]==v:
        return v
    else:
        parent[v]=find(parent[v])
        return parent[v]

사실 else밑으로 바로 return find(parent[v])을 편하게 구현했었다. 하지만 이렇게 구현하면

1<-2<-3<-4 일때 4의 부모를 찾으려면 4,3,2,1로 거슬러 올라가야 하지만 위의 코드같이 구현하면 1,2,3,4의 모든 부모노드가 1로 통일된다.이것을 경로 압축이라고 한다.

3.merge(병합)

def merge(a,b):
    x=find(a)
    y=find(b)
    if x==y:
        return
    else:
        if x < y:
            parent[y] = x
        else:
            parent[x] = y

작은 쪽을 기준으로 집합을 만들어 준다. a,b의 부모노드가 같지 않으면 병합시킨다.

 

4195 친구네트워크

https://www.acmicpc.net/problem/4195

1.접근

친구들 이름나오면 유니온파인드로 합쳐줘야겠다고 생각했다.

2.풀이

모든 아이들을 cnt 1로 초기화하고 병합할때 cnt의 값을 합친다

3.코드

	import sys
	input=sys.stdin.readline
	n=int(input())
	def find(x):
	if parent[x]==x:
	return x
	else:
	return find(parent[x])
	def merge(x,y):
	q=find(x)
	w=find(y)
	if q==w:
	print(cnt[w])
	elif q>w:
	cnt[w]+=cnt[q]
	parent[q]=w
	print(cnt[w])
	else:
	cnt[q]+=cnt[w]
	parent[w]=q
	print(cnt[q])
	for _ in range(n):
	m=int(input())
	parent ={}
	cnt={}
	for _ in range(m):
	a,b=list(input().split())
	if a not in parent:
	parent[a]=a
	cnt[a]=1
	if b not in parent:
	parent[b]=b
	cnt[b]=1
	merge(a,b)

view raw 4195친구.py hosted with ❤ by GitHub

4.배운점

• 경로압축을 항상 쓰도록 하자.
• 최소신장트리 알고리즘에 쓰인다.(사이클 방지를 위해)