BOJ 1922. 네트워크 연결하기(python)

BOJ 1922. 네트워크 연결하기(python)

문제링크

문제설명

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입출력 예

코드

import sys
input = sys.stdin.readline

# 최소 신장 트리
# 크루스칼 알고리즘
# 특정 원소가 속한 집합을 찾음
def find_parent(parent, x):
    # 루트 노트가 아니라면 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# Union 연산
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수
N = int(input())
# 간선의 개수
M = int(input())
# 부모 테이블 초기화
parent = [0] * (N + 1)
edges = []
result = 0
# 부모를 자기 자신으로 초기화
for i in range(N + 1):
    parent[i] = i

# cost 순으로 정렬하기 위해 cost를 앞으로 빼서 담음
for _ in range(M):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

# 간선 정보 cost 순으로 정렬
edges.sort()

# 간선을 돌며 체크
for edge in edges:
    cost, a, b = edge
    # 사이클을 생성하지 않으면 Union 연산을 수행하고 cost를 결과값에 담아준다.
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost
print(result)