[백준 / Python] 네트워크 연결_1922

 

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

내 풀이

n = int(input())
m = int(input())
 
parent = [i for i in range(n + 1)]
 
 
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]
 
 
def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    elif a > b:
        parent[a] = b
        
        
data = []
for _ in range(m):
    a, b, c = map(int, input().split())
    data.append((c, a, b))
    
data.sort()
 
 
def solved():
    result = 0
    for i in data:
        cost, x, y = i
        if find(parent, x) != find(parent, y):
            union(parent, x, y)
            result += cost
 
    print(result)
 
solved()
 

 

예를 들어, 그림과 같은 상황에서 2 - 3 을 이어주는 간선을 추가해도 되는지 판단하기 위해서는, 연결하려는 두 노드의 부모가 같으면 신장트리의 조건이 맞지 않게 된다.

 

+ 신장트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를의미한다.

 

 

 

 

Q2. 왜 union함수와 find함수를 사용해야 할까?

 

예전에 유니온 파인드 문제를 보고, 왜 굳이 union(), find()를 써야할까? 의문을 가진 적이 있었다.

이전의 그래프 문제를 해결할 때와 같이 각 간선의 정보를 리스트로 저장하여, 부모 노드가 같다면 같은 집합으로 판단하면 안되나?

하지만 이럴 경우, 한 노드당 최악의 경우 O(N) 시간 복잡도를 가진다. 하지만 union연산을 하면서 각 노드가 자신의 부모를 바로 가르키게 되면서 부모 노드까지 찾는 경로가 압축되어 더 효율적이다.