[파이썬, Python] 백준 16398번 : 행성 연결

백준 16398번 : 행성 연결

(문제 바로가기)

 

 

내 코드

import sys

input = sys.stdin.readline

def find_parent(parent, x):  # 부모 노드 찾기
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union(parent, a, b):  # 집합 합치기
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


n = int(input())  # 행성의 수
arr = [list(map(int, input().split())) for _ in range(n)]  # 각 행성간의 플로우 관리 비용
parent = [i for i in range(n)]  # 부모 노드 정보

edges = []  # 행성 간선 정보
# arr이 대각선(↘)을 기준으로 삼각형이 대칭이니
# 한쪽의 삼각형 부분 데이터만 간선 정보로 넣어주면 됨
for i in range(1, n):
    for j in range(i):
        edges.append((arr[i][j], i, j))
edges.sort()  # 행성 간선 정보를 최소 비용 순으로 정렬

answer = 0
for cost, a, b in edges:  # 크루스칼 알고리즘 수행
    if find_parent(parent, a) != find_parent(parent, b):  # 서로 같은 집합이 아닌 경우
        union(parent, a, b)  # 연결
        answer += cost

print(answer)  # 최소 플로우의 관리 비용