백준 4386 별자리 만들기

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/4386

풀이

난이도 : GOLD III

이 문제는 2차원 좌표 상에 여러 개의 점이 주어질 때, 두 점을 이은 선분들을 통해 모든 점이 이어져 있도록 하고, 그 중 선분의 길이가 가장 최소가 되도록 하는 결과를 구하는 문제이다.

문제를 보고, 최소 스패닝 트리의 문제로 크루스칼 알고리즘을 떠올렸다.

find_parent(parent, x) : x의 부모 노드를 찾음
union_parent(parent, a, b) : a와 b의 부모 노드를 합침

✔ 순서

1) 주어지는 점들을 모두 입력받는다.
2) 모든 점들을 보며 나올 수 있는 선분들을 모두 edges에 넣어준다. 이 때, 순서는 선분의 길이, x 좌표, y 좌표 순서로 넣어준다.(정렬을 편하게 하기 위해)
3) 선분들을 담은 edges를 길이가 작은 순서로 정렬한다.
4) 선분들을 작은 순서대로 하나씩 확인한다.
5) 이 때, 선분을 이루는 두 점 a와 b가 연결되어 있는지 확인한다. (find_parent)
6) 연결되어 있지 않다면 두 점을 연결해주면서 결과값(result)에 선분의 길이를 더해준다.
7) 최종적으로 나온 결과값을 출력한다.

코드

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())

vertex = []
edges = []
parent = [i for i in range(n + 1)]

for _ in range(n):
    vertex.append(list(map(float, input().split())))

for i in range(n):
    for j in range(i, n):
        if i == j:
            continue
        
        x = vertex[i][0] - vertex[j][0]
        y = vertex[i][1] - vertex[j][1]
        edges.append((round((x * x + y * y) ** 0.5, 2), i + 1, j + 1))

edges.sort()

result = 0
for edge in edges:
    dist, a, b = edge
    
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += dist

print(result)