[1922, 4386번 | 골드4, 3] 최소 신장 트리 2

1922번 네트워크 연결 문제는 이틀전에 풀었던 최소 스패닝 트리(1197번)과 똑같은 문제다.

복습 겸 풀어보았다.

#B1922 최소 스패닝 트리
import sys

def union_find(a, b): #루트(부모)를 찾아서 루트 번호가 더 작은 곳에 큰 루트번호를 붙임
    ah = get_parent(a)
    bh = get_parent(b)
    if ah>bh:
        parent[ah] = bh
    else:
        parent[bh] = ah

def get_parent(x):
    if parent[x]==x:#루트노드는 값이 루트의 번호
        return x
    parent[x] = get_parent(parent[x])
    return parent[x]


def same_parent(a,b):
    return get_parent(a) == get_parent(b)


input = sys.stdin.readline

N = int(input())
M = int(input())

li = [] # 간선리스트
parent = [i for i in range(N+1)]

for i in range(M):
    li.append(list(map(int, input().split())))

li = sorted(li, key = lambda x:x[2]) #크루스칼 알고리즘은 가중치가 작은 '간선'부터 택하기에 정
c=0
k=0
for v1, v2, l in li:
    if not same_parent(v1,v2):
        c+=1
        k+=l
        union_find(v1,v2)
        if c==N-1:
            break
print(k)

 

4386번 별자리 만들기 문제도 조금만 생각을 하면 쉽게 풀 수 있다.

 

 

전에 풀었던 두 문제처럼 "나 최소 스패닝 트리야" 이렇게 말하진 않지만 읽어보면 최소 스패닝 트리인 것을 알 수 있다.

다만 입출력이 정수가 아닌 실수라는점, 정점과 간선을 따로 정해주지 않고 좌표만 준다는 점이 문제이다.

 

여기서 당황하지 않고 문제를 한번더 읽어보면 별의 개수 n이 100이하인 것과 시간제한이 넉넉한 1초라는 것을 고려했을 때

"정점은 순서대로 번호를 매기고, 각 정점간의 거리를 통해 간선을 만들면 되겠군" 이렇게 떠올리면 끝이다.

import sys

def union_find(a, b):
    a = get_parent(a)
    b = get_parent(b)

    if a > b:
        parent[a] = b
    else:
        parent[b] = a

def get_parent(x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent[x])
    return parent[x]

def same_parent(a, b):
    return get_parent(a) == get_parent(b)

input = sys.stdin.readline

n = int(input())
li1 = []#별자리 좌표 리스트
parent = [i for i in range(n+1)]
for i in range(n):
    li1.append(list(map(float, input().split())))

li2 = []#간선 리스트 (별자리 간의)

#별 간의 경로를 다 구해 어차피 제한 시간 2초에 n은 최대 100이라 괜찮음
for i in range(n):
    for j in range(n):
        if i!=j:
            li2.append([i+1,j+1,round(((li1[i][0]-li1[j][0])**2+(li1[i][1]-li1[j][1])**2)**0.5,3)])
        
li2 = sorted(li2, key = lambda x:x[2])

l=0#간선n-1개 되면 탈출
k=0#가중치
for v1, v2, e in li2:
    if not same_parent(v1,v2):
        k+=e
        l+=1
        union_find(v1,v2)
        if l==n-1:
            break
print(round(k,2))