[백준] 16398번 행성 연결 파이썬 코드

코드

# 최소 스패닝 트리, 크루스칼 알고리즘 이용

def find(a, lst):
  if a != lst[a]:
    lst[a] = find(lst[a], lst)
  return lst[a]

def union(a, b,lst):
  a = find(a, lst)
  b = find(b, lst)
  if a < b:
    lst[b] = a
  else: lst[a] = b

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

n = int(input())
parent = [i for i in range(n+1)]
graph = [[*map(int, input().split())] for _ in range(n)]
edge = []
for i in range(n):
  for j in range(i+1,n):
    edge.append((graph[i][j],i,j)) # 각 지점 간의 비용과 정점을 찾아준다.
edge.sort()
res = 0
for i in range(len(edge)):
  if find(edge[i][1],parent) != find(edge[i][2],parent):
    res += edge[i][0]
    union(edge[i][1],edge[i][2],parent)
print(res)