악곱 == 악성곱슬

크루스칼

---

이 문제는 정점이 좌표로 이루어져 있다. 이를 통해 최소 신장 트리를 구현해야 한다. 보통 기본 유형은 노드 번호가 주어지고 노드간 거리가 주어지면 kruskal을 이용해서 최소 신장 트리를 구할 수 있었다.

다른 문제에 비해 까다로운 포인트

1. 부동 소수점으로 주어지는 input
2. 노드 번호가 아니라 좌표로 주어지는점
3. 소수점 둘째 자리에서 반올림 하는 점

위 세가지 까다로운 포인트를 해결하기 위해 우선 입력받은 좌표를 노드 번호로 맵핑해준다(2번 해결). 그리고 부동 소수점을 해결하기 위해서는 . ← 을 파싱해주는 방법과 그냥 map(float)를 해버리는 방법이 있다. 나는 후자로 구현했다. 이건 문제에서 주어지는 인풋 형식에 따라 다를 테니 그때그때 상황에 맞춰서 해야 한다. 마지막으로 둘째 자리에서 반올림 하는 것은 허용 오차가 주어진다. 10^-2임을 보아 그냥 round를 사용하면 될듯 하다.

따라서 위와 같은 까다로운 포인트를 통해 좌표계로 주어진 점은 기존 우리가 kruskal을 구현할 떄 사용하는 거리-노드번호 형태의 배열로 구현한 뒤 편하게 kruskal을 사용하면 된다. 코드는 아래와 같다.

구현

---

import sys

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

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

def get_distance(x1, y1, x2, y2):
    return round(((x1 - x2)**2 + (y1 - y2)**2)**0.5, 2)

def solution():
    edges = []
    for i in range(len(points)):
        for j in range(i+1, len(points)):
            dist = get_distance(points[i][0], points[i][1], points[j][0], points[j][1])
            edges.append([dist, points[i][2], points[j][2]])
    edges.sort()

    parent = [i for i in range(len(points))]
    answer = 0
    for dist, a, b in edges:
        if find(a, parent) == find(b, parent):
            continue
        parent = union(a, b, parent)
        answer += dist
    return answer

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    points = []
    for Idx in range(N):
        A, B = map(float, sys.stdin.readline().rstrip().split())
        points.append([A, B, Idx])
    print(solution())