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

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

1774번: 우주신과의 교감

---

💡 문제 풀이

최소 신장 트리 문제이다. 크루스칼 알고리즘으로 해결했다.

 

이 문제는 특이하게 각 정점에 대한 좌표가 주어지고 이미 연결된 간선의 정보를 준다.

우선 입력받는 순서가 정점의 순서이기 때문에 각 좌표를 저장한 이후에 간선의 정보를 만들어준다.

크루스칼 알고리즘이 (정점 개수 - 1)개 일 때 종료되니 이미 연결된 edge의 정보를 받을 때 세준다.

✔️ 느낀 점

문제 자체는 어렵지 않으나 시간 초과를 방지하기 위해서 우선순위 큐를 사용했다.

또한 중복된 데이터를 포함하고 있어서 이미 연결된 정점의 정보를 받을 때 중복된 값인지 체크해줘야한다.

💻 코드

import sys, heapq
input = sys.stdin.readline

N, M = map(int, input().split())
points = []
for _ in range(N):
    points.append(list(map(int, input().split())))

edges = []
for i in range(N):
    for j in range(i+1, N):
        dist = ((points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2) ** 0.5
        heapq.heappush(edges, [dist, i+1, j+1])

parent = list(range(N+1))

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

def union(x, y):
    x = find(x)
    y = find(y)
    
    parent[y] = x
    
cnt, ans = 0, 0

for _ in range(M):
    x, y = map(int, input().split())
    if find(x) != find(y):
        union(x, y)
        cnt += 1

while True:
    if cnt == N-1: break
    
    edge = heapq.heappop(edges)
    
    if find(edge[1]) != find(edge[2]):
        union(edge[1], edge[2])
        ans += edge[0]
        cnt += 1
        
print(f'{ans:.2f}')