악곱 == 악성곱슬

크루스칼

---

이 문제는 최소 신장 트리를 구해야 하는데 이미 연결된 노드가 정해져있을 경우에 대해 해결해보는 문제이다. 각 노드는 좌표로 주어져있다. 따라서 이 문제에서 고민해야 하는 점은 다음과 같다.

1. 좌표를 어떻게 노드로 둘 것인가
2. 좌표간의 거리를 어떻게 구할 것인가
3. 이미 연결된 노드를 어떻게 처리할 것인가

우선 1번에 대해서는 문제에서 들어오는 순서대로 번호를 매기면 된다고 알려준다. 그리고 2번에 대해서는 두 점의 좌표간의 거리를 피타고라스 정리를 이용해서 구하면 된다. 다만 숫자의 크기에 대해 고려할 필요가 있다. python3는 정수에 대해 arbitrary precision을 사용하기 때문에 오버플로우를 고려하지 않아도 된다. 마지막으로 3번에 대해서는 미리 union연산을 통해 거리를 더하지 않고 간선을 연결하면 된다.

그리고 모든 포인트에 대해 간선 길이를 구하고 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

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

def solution(n):
    edges = []
    parent = [i for i in range(n+1)]

    for a, b in already:
        union(a, b, parent)

    # 간선 길이 구하기
    for i in range(1, n):
        for j in range(i+1, n+1):
            dist = get_distance(points[i][0], points[j][0], points[i][1], points[j][1])
            edges.append([dist, i, j])

    edges.sort(key=lambda x: x[0])
    answer = 0
    for dist, a, b in edges:
        if find(a, parent) == find(b, parent):
            continue
        union(a, b, parent)
        answer += dist
    print(format(answer, ".2f"))

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().rstrip().split())
    points = [[]]
    already = []
    for idx in range(N):
        points.append(list(map(int, sys.stdin.readline().rstrip().split())))
    for _ in range(M):
        already.append(list(map(int, sys.stdin.readline().rstrip().split())))
    solution(N)