[파이썬] 백준 1922 : 네트워크연결 (골드4)

[파이썬] 백준 1922 : 네트워크연결 (골드4)

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

---

풀이

방향성 생각

• 모든 노드를 연결하는 최소 비용을 구하는 기본적인 MST 문제

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

N = int(input())
M = int(input())

# cost 내림차순 정렬
G = [tuple(map(int,input().split())) for _ in range(M)]
G.sort(key=lambda x:-x[2])
P = [i for i in range(N+1)]

def find(x):
    if P[x] != x:
        P[x] = find(P[x])
    return P[x]

answer = 0
# 간선 코스트 작은거부터 하나씩 연결하기
while G:
    a,b,cost = G.pop()

    pa,pb = find(a),find(b)
    if pa!=pb:
        P[max(pa,pb)] = min(pa,pb)
        answer += cost
print(answer)

코멘트

• .