[SWEA] 하나로

[SWEA] 하나로

Problem URL : 하나로

import sys
sys.stdin = open("input.txt", "r")

def find(x):
    if group[x] == x:
        return x
    group[x] = find(group[x])

    return group[x]


def union(x, y):
    x = find(x)
    y = find(y)

    if x != y:
        group[x] = y


T = int(input())

for tc in range(1, T+1):

    N = int(input())
    xList = list(map(int, input().split()))
    yList = list(map(int, input().split()))
    distance = []
    group = [i for i in range(N)]
    E = float(input())
    edges = []
    for i in range(N):
        for j in range(i + 1, N):
            d = (xList[i] - xList[j]) ** 2 + (yList[i] - yList[j]) ** 2
            edges.append((d, i, j))

    edges.sort()
    cnt = 0
    idx = 0
    answer = 0
    while cnt != N - 1:
        dist = edges[idx][0]
        start = edges[idx][1]
        end = edges[idx][2]
        if find(start) != find(end):
            union(start, end)
            answer += dist
            cnt += 1
        idx += 1

    answer = int(answer * E + 0.5)
    print('#{} {}'.format(tc, answer))

Comments

크루스칼 알고리즘이다.