[BOJ/Python] 4386_별자리 만들기

문제 출처:https://www.acmicpc.net/problem/4386

4386번: 별자리 만들기

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

예제 입력 1

3
1.0 1.0
2.0 2.0
2.0 4.0

예제 출력 1

3.41

---

풀이

 

모든 별들이 연결되어 있으면서, 두 별 사이의 거리의 합이 최소가 되도록 하였을 때 두 별 사이의 거리의 합을 출력하는 문제이다.

 

1. 별들은 입력받은 순서대로 0번,1번,...,n-1번이다.
2. 모든 별들에 대하여 다른 별과의 거리를 구한다. 총 n(n-1)/2 개의 거리를 구할 수 있다.
3. 두 별과 그 사이의 거리의 정보를 담은 리스트를 생성한다.
4. 이 리스트는 A->B로 가며 가중치가 C인 간선의 정보를 담는다고 생각하면 된다.
5. 가중치(두 별 사이의 거리)를 기준으로 오름차순으로 정렬한다.
6. 이 정보를 이용하여 크루스칼 알고리즘으로 최소 신장 트리를 구한다.

코드는 다음과 같다.

 

import sys
import math
 
def find_parent(parent,x):
    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]
 
def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
 
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
 
 
n = int(sys.stdin.readline())
stars = []
for _ in range(n):
    x,y = map(float,sys.stdin.readline().split())
    stars.append((x,y))
 
parent = [i for i in range(n)]
edges=[]
 
for i in range(n):
    for j in range(i+1,n):
        c = math.dist((stars[i][0],stars[i][1]),(stars[j][0],stars[j][1]))
        edges.append((i,j,c))
 
edges.sort(key=lambda x:x[2])
 
result = 0
l = 0
for a,b,c in edges:
    if find_parent(parent,a)!=find_parent(parent,b):
        union_parent(parent,a,b)
        result+=c
        l+=1
    if l==n-1:
        break
 
print(round(result,2))

• 이중 for문을 이용하여 별들 사이의 거리를 모두 구한다.
• 두 별과 사이의 거리의 정보를 담은 edges를 거리를 기준으로 오름차순으로 정렬한다.
• 거리가 제일 짧은 간선들부터 차례로 살펴보며, 두 별이 같은 집합에 속해있지 않다면 하나로 연결해 준다.
• 여기서 result는 출력해야 하는 두 별 사이의 거리의 합이다.
• l의 경우, 현재 연결한 별의 개수이다.
• l이 n-1이 되면 최소 신장 트리가 만들어졌음을 의미하기 때문에 더 이상 반복문을 진행하더라도 의미가 없으므로 break를 통해 반복문을 탈출한다.
• 최종적으로 result를 출력한다.