[백준 1922 네트워크 연결] - 파이썬 풀이 🦄

• 백준 1922 네트워크 연결 - 파이썬 풀이 🦄
  • 문제
  • Keypoints
  • Solution
  • References

백준 1922 네트워크 연결 - 파이썬 풀이 🦄

문제

Minimal Spanning Tree를 구하는 문제이다.

Keypoints

• minimal한 edge부터 선택하면서
• cycle을 만드는 경우를 제외하면 된다.
  • 두 꼭지점의 집합이 서로 같다면 합쳤을 때 Cycle을 만든다.

Solution

import sys 

n = int(input())
e = int(input())
graph = [list(map(int, sys.stdin.readline().strip().split())) for i in range(e)]
graph.sort(key=lambda x:x[2])
sets = [i for i in range(n+1)]

distance = 0
index = 0
while sum(sets) != n :
    a,b,d = graph[index]
    setA, setB = sets[a], sets[b]
    if setA !=setB:
        distance += d 
        setC = min(setA, setB)
        for i in range(1, n+1):
            if sets[i] in [setA, setB]:
                sets[i] = setC
    index +=1
print(distance)

References

Problem Link