백준 1774번 : 우주신과의 교감

https://www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

 

처음 풀어본 최소신장트리(MST) 문제이다.

 

문제를 요약하자면 N개의 점에 대한 2차원 좌표가 주어지고, 두 점을 잇는데 두 점 사이의 거리만큼 비용이 발생할 때 비용을 최소로 하면서 N개의 점을 모두 연결된 상태(특정한 점에서 다른 점까지 도달할 수 있음)로 만드려고 한다. 그런데 이때 처음부터 이미 이어져있는 점이 있을 수도 있다. 이때 필요한 최소 비용을 구하는 문제다.

 

가장 먼저 떠오른 접근 방법은 그리디였다. N이 최대 1000이므로 모든 점들 사이에 존재할 수 있는 간선의 최대 개수는 100만개를 넘지 않는다. 따라서 모든 간선에 대한 비용(두 점 사이의 거리)를 계산해서 두 점과 거리 정보를 리스트에 저장해두고 매번 가장 비용이 적은 간선부터 꺼내서 그 간선에 연결된 두 점을 하나의 그룹으로 만든다. 이때 처음부터 이어져있는 두 점은 간선의 비용을 0으로 리스트에 저장해서 가장 먼저 꺼낼 수 있도록 한다. 두 점을 합칠 땐 Union-Find 알고리즘처럼 두 점의 부모에 대한 정보를 갱신해줌으로써 구현했다. 리스트에서 꺼낸 두 점의 부모가 같다면 이미 두 점은 같은 그룹에 속해있으므로 비용을 더해 줄 필요가 없다.

 

문제를 다 풀고나서 깨달은 사실은 이런 방식을 크루스칼 알고리즘이라고 부른다고 한다. 최소신장트리 알고리즘 중 하나로 크루스칼 알고리즘과 프림 알고리즘이 있다.

import sys
input = sys.stdin.readline

def parent(i):
    if p[i] != i:
        p[i] = parent(p[i])
    return p[i]

def union(x, y):
    px = parent(x)
    py = parent(y)

    if px > py:
        p[px] = py
    else:
        p[py] = px

n, m = map(int, input().split())
q = []
p = list(range(n+1))
g = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    q.append((0, a, b))

for i in range(1, n+1):
    for j in range(i+1, n+1):
        if i == j:
            continue
        d = ((g[i][0] - g[j][0])**2 + (g[i][1] - g[j][1])**2)**0.5
        q.append((d, i, j))
q.sort()

r = 0
for d, a, b in q:
    if parent(a) != parent(b):
        union(a, b)
        r += d

print("%.2f"%r)