백준 5719 : 문제링크

  • 문제유형 :

    • 그래프
    • 크루스칼 알고리즘
  • 설명

    • 정점의 개수 N이 최대 1000이므로, 가능한 통로의 개수는 약 N^2이다
    • 크루스칼 알고리즘은 간선의 개수가 E일 때 O(ElogE)로 동작하므로 해결할 수 있다 (정렬 알고리즘 시간복잡도)
  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    import math
    import sys

    input = sys.stdin.readline

    def get_distance(p1, p2):
    a = p1[0] - p2[0]
    b = p1[1] - p2[1]
    return math.sqrt((a * a) + (b * b))

    def get_parent(parent, n):
    if parent[n] == n:
    return n
    return get_parent(parent, parent[n])

    def union_parent(parent, a, b):
    a = get_parent(parent, a)
    b = get_parent(parent, b)
    if a < b:
    parent[b] = a
    else:
    parent[a] = b

    def find_parent(parent, a, b):
    a = get_parent(parent, a)
    b = get_parent(parent, b)
    if a == b:
    return True
    else:
    return False

    edges = []
    parent = {}
    locations = []
    n, m = map(int, input().split())

    for _ in range(n):
    x, y = map(int, input().split())
    locations.append((x, y))

    length = len(locations)

    for i in range(length - 1)
    for j in range(i + 1, length):
    edges.append((i + 1, j + 1), get_distance(location[i], location[j]))

    for i in range(1, n + 1):
    parent[i] = i

    for i in range(m):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

    edges.sort(key=lambda data: data[2])

    result = 0
    for a, b, cost in edges:
    if not find_parent(parent, a, b):
    union_parent(parent, a, b)
    result += cost

    print("%0.2f" %result)