[유니온 파인드] 알고리즘

 

1.  개념

 

     유니온 파인드 알고리즘은 기본적으로 그래프 자료 구조를 이용한다

     Union( 노드를 한 집합으로 합치고 ) + Find( 선택한 노드가 포함되어 있는 집합의 대표 노드 찾기 )

     

     유니온 파인드 알고리즘을 사용하는 목적은 그래프를 정렬하여 시간 복잡도를 줄이는 데에 있다

     유니온 파인드 알고리즘으로 정렬한 그래프의 노드들은 대표 노드와 바로 연결된다

     

      이렇게 되면 추후 노드와 관련된 연산 속도가 O(1)로 변경된다

 

 

2.  유니온 파인드 알고리즘 구현

 

    1 )  초기 설정

 

           1차원 리스트를 이용해 노드를 정리한다

           리스트의 value는 index값으로 초기화한다

           처음에는 노드들이 모두 단절되어 있어서 각 노드가 대표 노드가 된다

index	1	2	3	4	5	6
value	1	2	3	4	5	6

      

 

    2 )  Union 연산

 

           두 노드를 선택해 하나의 집합으로 합치는 연산

           리스트에서 각 노드의 value를 대표 노드의 value로 통일해준다

 

           1번 노드와 4번 노드를 1번 집합으로 합치고, 5번 노드와 6번 노드를 합쳐보자

           -> 1번과 4번 노드의 value를 1로 통일, 5번과 6번 노드의 value를 5로 통일

index	1	2	3	4	5	6
value	1	2	3	1	5	5

            

            4번 노드와 6번 노드를 1번 집합으로 합쳐보자

            -> 4번과 6번 노드의 대표 노드인 1번과 5번 노드의 value를 1로 통일

index	1	2	3	4	5	6
value	1	2	3	1	1	5

   

 

    3 )  Find 연산

           특정 노드에 관해 그 노드가 속한 집합의 대표 노드를 반환하는 연산

           ( 1 )  노드를 하나 선택해주고 선택한 노드의 index값과 value가 동일한지 확인한다

           ( 2 )  동일하지 않으면 value가 가리키는 index로 이동한다

           value와 index값이 동일해질 때까지 ( 1 ) ~ ( 2 ) 반복   ->   재귀함수 이용

           이동한 노드의 value와 index값이 동일해지면 ( 대표 노드에 도달하면 ) 재귀함수를 빠져나온다

           Find 연산 과정에서 거치는 모든 노드의 value를 대표 노드값으로 변경한다

                      

           6번 노드에 Find 연산을 수행해보자

           -> index값(6)과 value(5)가 동일한지 확인 

           -> 동일하지 않으므로 value가 가리키는 index(5)로 이동

           -> index값(5)과 value(1)가 동일한지 확인

           -> 동일하지 않으므로 value가 가리키는 index(1)로 이동

           -> index값(1)과 value(1)가 동일한지 확인

           -> 동일하므로 재귀함수 빠져나옴

           -> Find 연산을 통해 거친 노드(6, 5, 1) 의 value를 1로 통일

index	1	2	3	4	5	6
value	1	2	3	1	1	1

 

 

 

3.  문제

 

# 1  집합 표현하기 - 백준 1717번

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

1717번: 집합의 표현

 

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
node = [] 

# 그래프 생성
for i in range(n+1):
    node.append(i)

# Union 연산
def Union(x, y):
	x = find(x)
    y = find(y)
    if x < y:	
        node[y] = x
    else:
        node[x] = y

# Find 연산
def Find(x):
	# index값과 value가 동일하면 재귀함수 빠져나오기
    if x == node[x]:
        return x
    # 재귀함수
    else:
        node[x] = Find(node[x])
        return node[x]


for i in range(m):
    act, a, b = map(int, input().split())
    if act == 0:
        Union(a, b)
    else:
        a = Find(a)
        b = Find(b)

        if a == b:
            print("YES")
        else:
            print("NO")

 

 

 

 

# 2  여행 계획 짜기 - 백준 1976번

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

1976번: 여행 가자

 

import sys

input = sys.stdin.readline

n = int(input())
m = int(input())

# 그래프 표현
adList = [0 for _ in range(n+1)]
for i in range(1, n+1):
    adList[i] = i

node = [[0 for _ in range(n+1)] for _ in range(n+1)]

connect = [] # Find 연산에서 거친 노드들 저장

result = True

# 인접 행렬 입력 받기
for i in range(1, n+1):
    num = list(map(int, input().split()))
    for j in range(1, n+1):
        node[i][j] = num[j-1]

# 여행 경로
route = list(map(int, input().split()))


# Union 연산
def Union(x, y):
    if node[x][y] == 1:
        while x != adList[x] or y != adList[y]:
            x = adList[x]
            y = adList[y]
        adList[y] = x


# Find 연산
def Find(x):
    if x == adList[x]:
        for i in connect:
            adList[i] = x
        return
    else:
        connect.append(x)
        Find(adList[x])


# 인접 행렬의 값이 1이면 Union 연산
for i in range(1, n+1):
    for j in range(1, n+1):
        Union(i, j)
# 여행 경로의 노드들에 대해 Find 연산
for j in range(1, m+1):
    connect.clear()
    Find(route[j-1])

# Find 연산을 통해 얻은 노드들의 대표 노드가 동일하면 YES, 다른 게 하나라도 있으면 NO 출력
answer = adList[route[0]]
for k in range(1, m):
    if answer != adList[route[k]]:
        result = False
        print("NO")
        break

if result:
    print("YES")

 

 

 

 

# 3  거짓말쟁이가 되긴 싫어 - 백준 1043번 

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

1043번: 거짓말

 

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
# 진실을 아는 사람의 수, 번호
truth = list(map(int, input().split()))
truth.pop(0)

# 그래프 표현
node = []
for i in range(n+1):
    node.append(i)

connect = [] # Find 연산 거친 노드들

party = [] # 파티에 참가하는 사람 수, 번호

total = 0 # 참가할 수 있는 파티 수


# Union 연산
def Union(x, y):
    while x != node[x] or y != node[y]:
        x = node[x]
        y = node[y]
    node[y] = x


# Find 연산
def Find(x):
    if x == node[x]:
        for i in connect:
            node[i] = x
        return
    else:
        connect.append(x)
        Find(node[x])


for i in range(m):
    number = list(map(int, input().split()))
    num = number.pop(0) # 파티 참가하는 사람 수
    if num == 2:
        Union(number[0], number[1])
    else:
    	# Union 연산 수행 - 사람 수가 3명 이상이면 골고루 연산 수행(i<j)
        for j in range(num):
            for k in range(j+1, num):
                Union(number[j], number[k])
    party.append(number)

# Find 연산 수행
for i in range(1, n+1):
    connect.clear()
    Find(i)

# 진실을 아는 사람의 대표 노드 저장
root_t = []
for i in range(len(truth)):
    root_t.append(node[truth[i]])

# 진실을 아는 사람의 대표 노드가 파티에 참가하는 사람의 대표 노드에 하나라도 포함되면 False
for i in range(len(party)):
    result = True
    for j in range(len(party[i])):
        if node[party[i][j]] in root_t:
            result = False
            break
    # True 면 total 증가
    if result:
        total += 1

print(total)