물대기(백준 1368)

  처음에는 만들 우물의 개수를 1부터 생각하면서 각각의 최소비용을 계산하려 했다. 하지만, 우물의 비용이 최소가 된다고 전체 비용이 최소가 되는 보장이 없다. 그래서 다른 블로그의 풀이법을 가져다가 풀었다. 

  우물을 파는 비용을 해당 번호와 0의 union이라 생각하고 풀어야 한다. 

import sys
input = sys.stdin.readline
 
N = int(input())
edge = []
cost = []
def find_parent(ind):
    if parent[ind] == ind:
        return ind
    parent[ind] = find_parent(parent[ind])
    return parent[ind]
 
 
def union(A,B):
    x = find_parent(A)
    y = find_parent(B)
 
    if x< y :
        parent[y] = x 
    else :
        parent[x] = y   
 
for i in range(N):
    pay = int(input())
    edge.append((pay,0,i+1))
 
arr = [list(map(int,input().split())) for _ in range(N)]
for i in range(N):
    for j in range(i):
        edge.append((arr[i][j],i+1,j+1))
 
 
parent = [i for i in range(N+1)]
edge.sort()
cnt = 0
result = 0
for pay,a,b in edge:
    if find_parent(a) != find_parent(b):
        cnt += 1
        result += pay
        union(a,b)
    if cnt == N:
        break
print(result)