~๋ชฉ์ฐจ~
๋ฌธ์
https://www.acmicpc.net/problem/19368
๋ฌธ์ ํด๊ฒฐ ํฌ์ธํธ
- ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ
์์ฑ ์ฝ๋
import sys
input = sys.stdin.readline
n = int(input())
edges = [] # ๋น์ฉ ์ค๋ฆ์ฐจ์์ ์ํ ๋ฆฌ์คํธ
parent = [i for i in range(n+1)] # ์๋ก์ ์งํฉ (๋ณธ์ธ์ ๋ถ๋ชจ๋ก ๊ฐ๋๋ก ์ด๊ธฐํ)
for i in range(n):
temp = list(map(int, input().split()))
for j in range(i+1, n): # ์ธ์ ํ๋ ฌ์ด ๋์นญ์ ์ด๋ฏ๋ก i+1๋ถํฐ n๊น์ง ์ ๋ณด๋ง ์๋ฉด ๋จ
edges.append((temp[j], i, j))
edges.sort() # ๋น์ฉ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์
def find_parent(x): # ๋ถ๋ชจ ๋
ธ๋ ์ฐพ๊ธฐ
if x != parent[x]:
parent[x] = find_parent(parent[x])
return parent[x]
def union_parent(a, b): # ๋ถ๋ชจ ๋
ธ๋ ํฉ์น๊ธฐ
a = find_parent(a)
b = find_parent(b)
if a < b:
parent[b] = a
else:
parent[a] = b
result = 0
for w, a, b in edges:
if find_parent(a) != find_parent(b): # ์ฌ์ดํด์ด ์๊ธฐ์ง ์๋๋ค๋ฉด
union_parent(a, b) # ๊ฐ์ ๋ถ๋ชจ(์งํฉ)์ผ๋ก
result += w # ๋น์ฉ ๊ณ์ฐ
print(result)
๋์์ด ๋์ จ๋ค๋ฉด ์ข์์ ๋๋ฌ์ฃผ์ธ์๐