[BOJ] 1717 집합의 표현

문제 링크

문제

문제풀이

• 입력으로 들어온 a,b를 연결해주는 작업

• a에 find연산, b에 find연산하여 b의 최상위에 있는 부모값을 a의 부모와 일치하게 만든다.

• 입력으로 들어온 a,b가 같은 부모를 가지고 있는지 ( 연결되어있는지) 확인 해서 같은 부모를 가지고 있다면 연결로 판단 같은 부모를 가지고 있지 않다면 연결 끊김으로 판단

• a가 p[a]와 일치한다면 최상위 부모노드라고 판단한다.

• a가 p[a]와 일치하지 않는다면, 최상위 부모노드를 찾기위해 p[a]값의 부모노드값을 찾아서 p[a]의 값으로 만든다.

p array

1 2 3 4 5 6 7
-------------
1 2 1 4 5 6 6

```
-> union(3, 7)
find(3) = 3의 부모값은 1, 그러므로 값이 다르니까
find(p[3])인 find(1)호출 1의 부모값은 1, 그러므로 값이 같으니까

1 리턴 ( 3의 최상위 부모 노드 )

find(7) -> 7의 부모값은 6, 그러므로 값이 다르니까
find(p[7])인 find(6) 호출, 6의 부모값은 6, 그러므로 값이 같으니까
6 리턴 ( 7의 최상위 부모 노드 )

그리고 p[pb] = pa , 
최상위 부모노드의 큰 값이 작은 부모를 따라게끔 연결 하기 떄문에

p[6] = 1

1 2 3 4 5 6 7
--------------
1 2 1 4 5 1 6 

이상태에서
7이 1과 연결되어있는지 확인하고 싶다면? 

find(1)과 find(7)이 일치하는 경우 ( 같은 최상위 부모노드를 가지고 있는 경우 )

find(1) == 1 ( 부모와 최상위 부모노드 값이 일치 )

find(7) 은 6 ( 부모와 최상위 부모노드 값이 일치 하지 않으므로 )
find(6)을 호출하고 그 값을 p[7[에 저장 ( path compression ) (2번 리턴)

find(6)은 1 ( 부모와 최상위 노드 값이 일치 하지 않으므로 )
find(1) 호출하고 그 값을 p[6]에 저장 == 1 리턴 (path compression) (1번 리턴) 

이때 재귀 방식이므로 path compression()은 역으로 호출됨

그러므로 find(1), find(7)을 호출하고 난 이후 p배열은 이 됨
1 2 3 4 5 6 7
--------------
1 2 1 4 5 1 1 

그리고 find(1) -> 1, find(7) -> 1이기 때문에 같은 집합이라고 판단

```

import sys
sys.setrecursionlimit(10**6)

input = sys.stdin.readline

V, E = map(int, input().split())

p = [i for i in range(V+1)]

li = []

for _ in range(E):
    A,B,C = map(int, input().split())
    
    li.append((A, B, C))

li.sort(key=lambda x:x[2]) # value기준 오름차순 정렬


def find(node):
    if node == p[node]: # 최상위 노드인경우
        return node
    
    p[node] = find(p[node]) # path compression
    return p[node] # 압축한 경로

def union(a, b):
    pa = find(a)
    pb = find(b)
    p[pb] = pa # 낮은순으로 정렬
    # pb = b의 최상위 부모 노드의 값
    # pa = a의 최상위 부모 노드의 값
    # p[pb] = pa
    # pb의 부모가 가지는 값을 pa로 바꿈
    # 즉, pa와 pb가 공통의 pa를 가짐으로써 둘이 연결
    
weighted_value = 0
count = 0

for item in li:
    if count == len(p)-1: # mst 완성
        continue 
    A, B, C = item
    
    if A > B: # 작은게 무조건 앞으로
        temp = A
        A = B
        B = temp
        
    if find(A) != find(B): # not cycle
        union(A, B)
        weighted_value += C
        count += 1
        
print(weighted_value)

• O(Mlog*N) ⇒ (Path Compression) FInd의 경우 O(1)

• M은 간선, N은 노드

입력

출력

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

NO
NO
YES

알고리즘 분류

• 자료 구조

• 분리 집합