[Python] BOJ 1774 - 우주신과의 교감

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

1774번: 우주신과의 교감

# 크루스칼을 이용한 MST로 풀었다.

 

1. 우선 N개의 좌표를 모두 입력받은 뒤, 좌표들끼리의 길이를 dist함수로 구한다.

 

2. graph에 (i, j, dist(i, j))를 넣어준다음 dist(i, j)순으로 오름차순 정렬해준다.

 

3. 이미 연결되어 있는 통로들은 union 해준 뒤 graph에서 연결이 안되어있는 통로들을 연결하며

   answer에 길이를 더해준다.

 

import sys
input = sys.stdin.readline
def find(c):
	if par[c] == c:
		return c
	else:
		par[c] = find(par[c])
	return par[c]
 
def union(a, b):
	a, b = find(a), find(b)
	par[max(a, b)] = min(a, b)
 
def check(a, b):
	return find(a) == find(b)

# a통로와 b통로의 거리를 구하는 함수
def dist(a, b):
	return ((a[0] - b[0])**2 + (a[1] - b[1])**2)**(1/2)

N, M = map(int,input().split())
par = [i for i in range(N)]
coordinate, graph = [], []
answer = 0
for _ in range(N):
	x, y = map(int,input().split())
	coordinate.append((x,y))
# 이미 연결되어 있는 통로 union해주기
for _ in range(M):
	x, y = map(int,input().split())
	union(x-1, y-1)

# 각 통로들 사이의 거리를 구해서 graph에 넣는 과정
for i in range(N-1):
	for j in range(i+1, N):
		graph.append((i, j, dist(coordinate[i], coordinate[j])))
# 거리순으로 오름차순 정렬
graph.sort(key= lambda x: x[2])
for i in graph:
	if not check(i[0], i[1]):
		union(i[0], i[1])
		answer += i[2]
print('%.2f' %(answer))

(solved.ac 티어: 골드4)

 

# 처음에 모든 통로들 사이의 거리를 구하는 과정에서 시간초과가 나지 않을까 생각했는데

   N이 최대 1000이라 구해야하는 통로들 사이의 거리 갯수는 최대 ₁₀₀₀C₂ = 499500개 라서

   그냥 모든 통로들 사이의 거리를 구한뒤 MST를 썼다.