[테스트케이스 추가] 백준 16398 번: 행성연결, python 파이썬

1. 문제

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

16398번: 행성 연결

 

2. 풀이

 

3. 구현

# 최소한의 비용으로 모든 행성을 잇는 간선을 만든다

import sys
# sys.stdin=open('input.txt')
import heapq
sys.setrecursionlimit(10**8)

n = int(sys.stdin.readline().strip())

gph=[]
for i in range(n):
    gph.append(list(map(int, sys.stdin.readline().strip().split())))



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

edges=[]
for i in range(n):
    for j in range(n):
        heapq.heappush(edges, (gph[i][j], i, j))
cnt=0
answer=0
while edges:
    w,s,e = heapq.heappop(edges)
    if find(s, parent)!=find(e,parent):
        uni(s,e,parent)
        answer+=w
        cnt+=1
    if cnt==n-1:
        break

sys.stdout.write(str(answer))

 

4. 테스트케이스 추가

 

5
0 5 4 3 12
5 0 12 8 3
4 12 0 9 3
3 8 9 0 15
12 3 3 15 0

답: 13

 

 

10
0	18	5	10	5	12	13	7	18	9
18	0	5	9	15	10	20	14	3	13
5	5	0	13	7	20	0	15	7	16
10	9	13	0	1	2	17	19	5	4
5	15	7	1	0	0	12	11	4	12
12	10	20	2	0	0	14	17	12	2
13	20	0	17	12	14	0	1	20	14
7	14	15	19	11	17	1	0	18	6
18	3	7	5	4	12	20	18	0	14
9	13	16	4	12	2	14	6	14	0

답: 21

 

 

10
0	8	0	0	1	1	8	5	3	2
8	0	2	0	1	8	8	2	4	2
0	2	0	4	1	6	7	5	1	7
0	0	4	0	6	1	8	3	2	2
1	1	1	6	0	4	5	4	0	3
1	8	6	1	4	0	4	7	5	3
8	8	7	8	5	4	0	1	6	3
5	2	5	3	4	7	1	0	5	6
3	4	1	2	0	5	6	5	0	8
2	2	7	2	3	3	3	6	8	0

답: 7

 

 

14
0	12	18	9	16	9	16	8	15	16	13	8	19	15
12	0	12	4	5	19	11	17	0	10	17	11	16	10
18	12	0	20	10	12	1	19	13	2	18	3	12	4
9	4	20	0	2	13	17	11	8	0	18	12	15	6
16	5	10	2	0	0	2	4	7	5	1	19	20	1
9	19	12	13	0	0	0	4	15	18	10	0	19	8
16	11	1	17	2	0	0	16	16	0	14	13	19	11
8	17	19	11	4	4	16	0	12	0	4	1	15	17
15	0	13	8	7	15	16	12	0	18	18	13	5	3
16	10	2	0	5	18	0	0	18	0	2	7	9	1
13	17	18	18	1	10	14	4	18	2	0	13	6	11
8	11	3	12	19	0	13	1	13	7	13	0	6	8
19	16	12	15	20	19	19	15	5	9	6	6	0	12
15	10	4	6	1	8	11	17	3	1	11	8	12	0

답: 19