https://www.acmicpc.net/problem/4386
문제
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.
- 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
- 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.
입력
첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)
둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.
출력
첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.
예제
조건
- 시간 제한: 1초
- 메모리 제한: 128MB
코드
import sys, math
input = sys.stdin.readline
# Union Find
def find(x):
if parent[x] == x:
return x
else:
return find(parent[x])
def union(a,b):
a = find(a)
b = find(b)
if a < b:
parent[b] = a
else:
parent[a] = b
# Input
N = int(input())
stars = [list(map(float,input().split())) for _ in range(N)]
parent = list(range(N+1))
paths = []
# 모든 별들 간의 거리 계산
for i in range(N-1):
for j in range(i+1,N):
distance = math.sqrt((stars[j][0] - stars[i][0])**2 + (stars[j][1] - stars[i][1])**2)
paths.append((distance,i,j)) # 거리, 시작 노드, 끝 노드
# 오름차순 정렬
paths.sort()
# Kruskal Algorithm
result = 0
for d,a,b in paths:
if find(a) != find(b):
union(a,b)
result += d
# Output
print(round(result,2))
- 유니온 파인드와 크루스칼 알고리즘을 이용하여 해결할 수 있는 문제이다.
- 하지만 다른 점은, 두 노드의 번호와 가중치를 입력 받은 것이 아니라, 2차원 형태에서 별의 좌표만을 받았다는 점이다.
-
입력이 실수로 들어오기 때문에,
int가 아닌float형태로 받아야한다. -
별을 최소 거리로 이어주기 위해서는, 각 별들간의 거리를 계산한 후에 최소 거리로 정렬해주는 과정이 필요하다.
- 모든 별들 간의 거리 계산을 진행한다.
-
여기서
i는 출발 노드,j는 도착 노드가 된다. -
두 점 사이의 거리 공식을 활용하여 거리
distance를 구해준다. -
정렬을 쉽게 하기 위해서, 거리, 출발 노드, 도착 노드 순으로
paths에 넣어준다. -
이제 기존 문제들처럼 두 노드의 번호와 가중치(거리)를 담은
paths리스트를 생성하였다.
Kruskal Algorithm을 사용하여 결과값result를 구한다.
- 정답은
round함수를 활용하여 소수점 둘째자리까지 출력한다.
느낀 점 & 배운 점
-
기존에 친절하게 노드의 번호와 가중치를 알려주었던 것과 다르게, 좌표만을 알려주어 조금은 당황했었던 문제이다.
-
별의 개수가 많지 않아 모든 거리를 구해주는 방식으로 풀 수 있었지만, 개수가 더 많아졌을 때는 시간 초과 & 메모리 초과를 피하기 위한 방법을 생각해야 할 듯 하다.
