[baekjoon] 백준 1922번(파이썬): 네트워크 연결

문제

1922번: 네트워크 연결

알고리즘

- 유니온-파인드를 통해 문제를 수행한다.

- 간선들의 가중치를 기준으로 정렬하여 최소 스패닝 트리의 가중치를 구한다.(비용)

- 반복문을 통해 두 간선들의 두 정점을 유니온-파인드를 통해 확인한다.

- 두 정점의 부모 노드가 같지 않다면 스패닝 트리인 것이다.

- 부모 노드가 같지 않은 두 정점을 작은 루트 노드를 기준으로 합친다.

코드

import sys


# 부모 노드 찾기
def find(p):
    if p == parent[p]:
        return p

    parent[p] = find(parent[p])
    return parent[p]


# 트리 합치기
def union(x, y):
    x = find(x)
    y = find(y)

    if y < x:
        parent[x] = y
    else:
        parent[y] = x


n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
graph.sort(key=lambda x : x[2])
parent = [i for i in range(n+1)]
answer = 0

for a, b, c in graph:
    if find(a) != find(b):
        union(a, b)
        answer += c


print(answer)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법