백준: 네트워크 python 파이썬

1. 문제

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

1922번: 네트워크 연결

2. 풀이

크루스칼 알고리즘의 풀이:

1. 간선을 cost 기준으로 오름차순(작->큰) 정렬

2. 연결이 안되어있으면 union + weight추가

3. 간선 v-1개가 연결되면 종료 (이번 문제에선 3번 제외)

 

3. 구현

import sys
import heapq

# sys.stdin = open("input.txt")

n = int(sys.stdin.readline())
edge = int(sys.stdin.readline())
edges=[]

parent=[i for i in range(n+2)]

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

def uni(x,y, parent):
  x = find(x, parent)
  y = find(y, parent)
  if x==y:
    return
  else:
    parent[x]=y
  return

while edge:
  s,e,w = map(int, sys.stdin.readline().split())
  heapq.heappush(edges, (w,s,e))
  edge-=1

answer=0

while edges:
  w,s,e = heapq.heappop(edges)
  # print(w,s,e)
  if find(s,parent) != find(e,parent):
    uni(s,e,parent)
    answer+=w

print(answer)