[Python] 백준 4386 - 별자리 만들기

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

4386번: 별자리 만들기

 

 

최소스패닝 트리를 만드는 크루스칼 문제다.

전형적인 크루스칼 문제라서 개념을 아는 사람이라면 쉽게 풀 수 있다.

import math

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(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())
star = [0]
for i in range(n):
    a,b = map(float, input().split())
    star.append((a,b))

parent = [i for i in range(n+1)] # 부모 테이블 초기화

# 모든 간선 정보를 입력받기
edges = []
for i in range(1,n):
    for j in range(i+1,n+1):
        cost = math.sqrt((star[i][0]-star[j][0])**2 + (star[i][1]-star[j][1])**2)

        edges.append((cost,i,j))
edges.sort()

result = 0

# 간선을 하나씩 확인
for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent, a, b)
        result+=cost

print(result)

 

DP문제 고민하다가 잘 안풀려서 이걸로 넘어왔는데... DP 너무 어려워ㅜ

DP에 시간투자 좀 해야겠다.

 

공부할수록 부족한 점이 계속 보여서 공부를 멈출 수가 없다.