그래프-유니온 파인드

이론

📖 유니온 파인드

• 여러 노드가 있을 때, 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find연산으로 구성되어있는 알고리즘.

📖 union연산
각 노드가 속한 집합을 1개로 합치는 연산.
집합에서 합집합을 의미한다.

📖 find연산
특정 노드 a가 속한 집합의 대표노드를 반환하는 연산.
자신이 속한 집합의 대표노드를 찾는 연산. -> 시간복잡도를 줄일 수 있다.

📖 유니온 파인드 알고리즘 구현 방법.

• 처음에는 노드가 연결되어 있지 않고 독립적이므로 각 노드가 대표노드가 된다. -> 1차원 리스트를 이용하여 표현. -> 리스트는 자신의 인덱스값으로 초기화한다.

• 2개의 노드를 선택해 각각의 대표노드를 찾아 연결하는 union연산을 수행한다.
  cf) 1,4 / 5,6 를 union 연산으로 연결하면,
  union(1,4) = [1,2,3,4,5,6] -> [1,2,3,1,5,6]
  union(5,6) = [1,2,3,1,5,6] -> [1,2,3,1,5,5]
  이 상태에서 union(4,6)을 수행하게 되면,
  4의 대표노드는 1, 6의 대표노드는 5 이므로
  union(4,6) = [1,2,3,1,5,5] -> [1,2,3,1,1,5] 가 된다.

문제풀이

📖 백준 1717 (🔗백준 1717 문제)

import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000)

n,m=map(int,input().split())
parent=[0]*(n+1)

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

def union(a,b):
    a=find(a)
    b=find(b)
    if a!=b:
        parent[b]=a

def check(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return True
    else:
        return False

for i in range(0,n+1):
    parent[i]=i

for i in range(m):
    q,a,b=map(int,input().split())

    if q==0:
        union(a,b)
    elif q==1:
        if check(a,b):
            print("YES")
        else:
            print("NO")

📖 백준 1043 (🔗백준 1043 문제)

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
true=list(map(int,input().split()))
true_n=true[0]                             # 진실을 아는 사람의 수
del true[0]                                # true 에서 del true[0] 하면, 진실을 아는 사람들의 번호
parent=[0]*(n+1)
party=[[] for i in range(m)]
result=0

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

def union(a,b):
    a=find(a)
    b=find(b)
    if a!=b:
        parent[b]=a

def check(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return True
    else:
        return False

for i in range(m):
    party[i]=list(map(int,input().split()))
    del party[i][0]

for i in range(n+1):
    parent[i]=i

for i in range(m):
    first=party[i][0]
    for j in range(1,len(party[i])):
        union(first,party[i][j])

for i in range(m):
    bool=True
    first=party[i][0]
    for j in range(len(true)):
        if find(first)==find(true[j]):
            bool=False
            break
    if bool==True:
        result+=1

print(result)

◼ 참고사항

• Do it! 알고리즘 코딩테스트
• 백준
• 동빈나 유투브 [합집합 찾기- 실전 알고리즘 강좌]