[Python] 백준 4386 별자리 만들기 | 크루스칼 알고리즘

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

4386번: 별자리 만들기

 

 

문제 해결 포인트

- 크루스칼 (최소 스패닝 트리) 알고리즘

- alist : 각 정점의 x, y 정보 저장

- edges : 정점 간 모든 간선 길이( sqrt((x1 - x2)**2 + (y1 - y2)**2) ) 를 오름차순으로 저장

- parent : 집합정보 ( 연결된 정점 정보)

 

- find 함수 : 같은 집합에 속해있는지 확인

- union 함수 : 같은 집합에 속하도록 parent 리스트 업데이트

 

- 정렬된 edges를 순차적으로 접근하며 사이클이 발생하지 않는다면 연결

 

 

작성 코드

import math
import sys
input = sys.stdin.readline

n = int(input())
alist = []
edges = []
parent = [i for i in range(n+1)]
for _ in range(n):
    x, y = map(float, input().split())
    alist.append((x, y))

for i in range(n):
    for j in range(i+1, n):
        x1, y1 = alist[i]
        x2, y2 = alist[j]
        edges.append((math.sqrt((x1 - x2)**2 + (y1 - y2)**2), i, j))

edges.sort()

def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

result = 0
for w, a, b in edges:
    if find(a) != find(b):
        union(a, b)
        result += w

print(round(result, 2))

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚