[백준 1922번] 네트워크 연결 문제 풀이 (with Python)

 

 

< 문제 >

 

 

< 입출력 >

1922번: 네트워크 연결 (acmicpc.net)

1922번: 네트워크 연결

 

 

 

 < 풀이 >

 

parent = [ i for i in range(노드 수 +1) ] 로 루트 노드를 저장하는 배열을 만든다.

루트 노드가 다른 것은 연결이 안되었다는 뜻이므로, 비용이 작은 순으로 정렬하고 루트 노드가 다른 경우 연결하였다. 

 

 

< 코드 >

import sys

input = sys.stdin.readline


def find(a):                  # 루트 노드 찾기 
    if a == parent[a]:        # 루트 노드가 자신인 경우, 자기 자신 반환
        return a
    parent[a] = find(parent[a])   
    return parent[a]               


def union(a, b):              # 두 노드 연결하기 
    a = find(a)               
    b = find(b)
    if b < a:                 # 두 노드 중 루트 노드가 작은 것을 두 노드의 루트 노드로 삼음
        parent[a] = b         
    else:
        parent[b] = a


arr = []
N = int(input())
M = int(input())
parent = [i for i in range(N + 1)]   # 루트 노드 초기화
result = 0      

for _ in range(M):
    a, b, c = map(int, input().split())  
    arr.append((a, b, c))

arr.sort(key=lambda x: x[2])         # 비용이 작은 순서대로 정렬
for a, b, c in arr:
    if find(a) != find(b):           # 루트 노드가 다른 경우 두 노드 연결하기
        union(a, b)
        result += c
print(result)