[Beakjoon] 1922. 네트워크 연결

🔗 Problem Link

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

---

❔Thinking

• 모든 컴퓨터가 연결되어야 할 때, 최소한의 비용을 반환한다.
• 각 컴퓨터를 연결하는 비용이 주어진다.

---

💻Solution

import sys
import heapq
input = sys.stdin.readline

N = int(input().rstrip())
M = int(input().rstrip())
lines = []
for _ in range(M):
    a,b,c = map(int, input().split())
    heapq.heappush(lines, (c,a,b))

def find_parent(x, parent):
    if x != parent[x]:
        parent[x] = find_parent(parent[x], parent)
    return parent[x]

def union(a,b,parent):
    a = find_parent(a, parent)
    b = find_parent(b, parent)
    parent[max(a,b)] = min(a,b)

total_cost = 0
parent = [i for i in range(N+1)]
while lines:
    cost, a, b = heapq.heappop(lines)
    if find_parent(a,parent) != find_parent(b,parent):
        union(a,b,parent)
        total_cost += cost
        
print(total_cost)

---

🗝️keypoint

1. 모든 컴퓨터를 최소 비용으로 연결하는 방법은, 가장 적은 비용의 연결부터 해나가는 방법이다.
2. '최소 신장 트리' 알고리즘으로 해결할 수 있으며, 각 연결 여부는 union-find로 확인할 수 있다.