[백준] 1197번 최소 스패닝 트리(python)

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

1197번: 최소 스패닝 트리

 

1. 난이도 골드4 (🥇)

import sys
input = sys.stdin.readline

v,e = map(int, input().rstrip().split()) #v정점 e간선

parent = [i for i in range(v+1)]
edges = []
result = 0

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

def union(a,b):
  a = find(a)
  b = find(b)

  if a<b:
    parent[b] = a
  else:
    parent[a] = b

for i in range(e):
  a,b,cost = map(int, input().rstrip().split())
  edges.append((cost,a,b))

edges.sort()

for edge in edges:
  cost,a,b = edge

  if find(a) != find(b):
    union(a,b)
    result += cost

print(result)

 

최소 스패닝 트리의 개념을 익히고 바로 풀어봤다.

 

간선을 오름차순 정렬하고 문제를 푸는 걸 깜박해서 틀렸었음 ㅜㅜ