유니온파인드 - #4195 친구 네트워크, #16562 친구비

✅ 같은 그래프에 속해 있는지 아닌지에'만' 관심 있을 때 유니온파인드를 사용하면 이를 손쉽게 알아낼 수 있다.

연결 순서가 중요한 경우라면 유니온파인드 알고리즘을 사용할 수 없다. 경로압축 과정에서 그래프의 모양이 변하기 때문에, 어떤 순서로 연결되었는지에 대한 정보가 유실된다.

코드

def union(a,b): 
	# a,b간의 관계를 disjoint set 자료구조로 나타낸다.
	# a가 속한 집합과 b가 속한 집합을 합집합 연산한다.
	A = find(a)
	B = find(b)
	if A<B: parent[B]=A
	else: parent[A]=B

def find(a): # a의 루트노드를 찾는다.
	if parent[a]!=a:
		parent[a]=find(parent[a])
	return parent[a]

활용

• A,B 사이에 edge가 존재한다 == A,B가 연결되어 있다 == union(A,B)
• find 연산의 결과가 같다 == 두 노드가 같은 그래프에 속해 있다 == 두 노드가 연결되어 있다
• A-B 간선 정보가 주어지고, union 연산 전 find(A),find(B)를 했는데 루트노드가 서로 같다면 사이클이 발생했다는 걸 의미한다. 이미 같은 그래프에 속해 있는 두 노드에 간선 하나가 추가된 것이기 때문에, N개의 노드 N-1개의 간선이라는 트리 조건이 깨지게 된다.

시간복잡도

이코테 책에 다음과 같이 나와 있다.

노드의 개수가 1,000개이고, union 및 find 연산이 총 100만 번 수행된다고 하자. 그럼 대략 1,000만 번 가량의 연산이 필요하다고 이해하면 된다.

대략적인 계산 방법은
노드 개수: V, union 연산 횟수: V-1, find 연산 횟수: M일 때 $V+M*log_{2}M$ 이다.

문제풀이

#4195 친구 네트워크

'친구 관계가 생길 때마다' 네트워크에 몇 명이 있는지를 출력해야 한다는 점이 포인트였다.

'네트워크에 몇 명이 속해있는지'는 결국 a가 속한 disjoint set에 노드가 몇 개 인지를 묻는 것이다.

♥ 처음 접근 방식

1. a-b 간선이 입력으로 들어오면 union 한다.
2. a가 속한 집합의 노드 개수를 카운트 하기 위해 a와 동일한 루트노드를 가지는 노드의 개수를 센다.

• 여태 추가된 모든 노드를 순회하면서 find연산을 한다.
• 이때 find연산의 결과로 리턴된 루트노드가 a의 루트노드와 같으면 cnt를 증가 시킨다.

결과: 시간초과

해당 방식의 경우 한 테스트케이스 당 노드 개수 만큼의 find 연산이 이뤄진다.
10^5개의 간선이 전부 다른 사람일 경우 노드의 개수는 10^5개가 된다.
10^5개 입력 당 매번 최대 10^5번의 find 연산이 일어난다면?
그래서 여기서 시간초과가 났던 것 같다. 시간복잡도 계산 너무 어려워...

♥ 새로운 접근 방식

union이 두 집합의 합집합 연산이라는 점을 활용했다.
union(a,b) = a가 속한 집합 ⋃ b가 속한 집합 이라는 뜻이므로, 각 집합에 속한 노드 개수를 관리하는 배열을 만들고(nums) union 연산 시에 해당 배열을 업데이트 했다.

def union(a,b,nums):
	A = find(a)
	B = find(b)
	if A<B: 
		parent[B]=A
		nums[A]+=nums[B]
		nums[B]=0
	elif A>B: # 이미 같은 집합일 경우 합칠 필요가 없으므로 else가 아닌 elif
		parent[A]=B
		nums[B]+=nums[A]
		nums[A]=0

else로 작성할 경우 A<B가 아닌 모든 경우를 포괄한다는 뜻이 되므로, elif로 작성해야 한다.
여기서 한 번 틀렸다.

♥ 전체 코드

import sys
def union(a,b,nums):
	A = find(a)
	B = find(b)
	if A<B: 
		parent[B]=A
		nums[A]+=nums[B]
		nums[B]=0
	elif A>B: # 이미 같은 집합일 경우 합칠 필요가 없으므로 else가 아닌 elif
		parent[A]=B
		nums[B]+=nums[A]
		nums[A]=0
		
def find(a):
	if parent[a]!=a:
		parent[a]=find(parent[a])
	return parent[a]

T =  int(sys.stdin.readline())

for _ in range(T):
	idx=0
	dic={}
	nums=[]
	parent=[]
	F = int(sys.stdin.readline())
	
	for _ in range(F):
		na,nb = list(sys.stdin.readline().split())
		if dic.get(na) is None:
			dic[na]=idx
			nums.append(1)
			parent.append(idx)
			idx+=1
		if dic.get(nb) is None:	
			dic[nb]=idx
			nums.append(1)
			parent.append(idx)
			idx+=1
		a = dic.get(na)
		b = dic.get(nb)
		union(a,b,nums)
		r = find(a)
		print(nums[r])

#16562 친구비

위에 문제 풀고 나서 풀어서 낭패 본 문제. 쉬운 문제였는데 어렵게 접근했다.

위 문제와 달리 '간선이 입력 될 때마다' 네트워크에 속한 친구 수를 출력해줄 필요가 없기 때문에, 일단 모든 간선을 입력 받아 그래프를 완성시킨 다음 모든 그룹을 친구로 만들 수 있는지를 판단하면 되는 문제였다. 친구 관계가 입력될 때마다 해당 친구들을 친구로 만들 수 있는지를 판단하다 보니 놓치는 케이스가 생겼다.

모든 union 연산을 하고 나면 친구 그룹별로 서로소 집합이 형성된다.
집합 별로 가장 싼 친구를 고르고, 집합별 가장 싼 친구의 친구비를 모두 더했을 때 k보다 작으면 준석이는 모두와 친구가 될 수 있다.

간선 마다 정보를 출력할 필요가 없다면 일단 모든 그래프를 완성 시킨 다음 접근하는 게 현명하다.

♥ 전체 코드

import sys
# 모든 union 연산을 한다
# 루트 노드가 같은 노드 중 가장 작은 비용을 더한다
# 다 더한 값이 k보다 작으면 모두와 친구가 될 수 있다.

def union(a,b):
	A = find(a)
	B = find(b)
	if A<B: parent[B]=A
	elif A>B: parent[A]=B
		
def find(a):
	if parent[a]!=a:
		parent[a]=find(parent[a])
	return parent[a]

N, M, k = list(map(int, sys.stdin.readline().split()))
cost = list(map(int, sys.stdin.readline().split()))
parent = [i for i in range(N)]
min_cost = [10001]*N

for _ in range(M):
	a,b = [i-1 for i in list(map(int,sys.stdin.readline().split()))]
	union(a,b)

for a in range(N):
	A = find(a)
	if cost[a]<min_cost[A]:
		min_cost[A]=cost[a]

total = 0
for cost in min_cost:
	if cost!=10001: total+=cost

if total<=k: print(total)
else: print("Oh no")