[Algorithm] BaekJoon : 4386. 별자리 만들기 by Python

djagmlrhks3·2021년 2월 22일
0

Algorithm

목록 보기
103/128
post-thumbnail

[문제 바로가기] https://www.acmicpc.net/problem/4386

📌문제 설명

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

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

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

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

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

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


💡 문제 풀이

**최소 신장 트리(MST : Minimum Spanning Tree)**를 구하는 문제다.

문제에서 좌표만 주어지고 비용이 주어지지 않아서 어떻게 MST를 만들까 고민하였는데

별의 개수가 100개 이하로 큰 편이 아니기 때문에 모든 별들의 거리를 구하여 (거리, 별1, 별2) 형태의 자료를 heap에다 넣어 MST를 만들었다.

MST는 크루스칼(Kruskal) 알고리즘으로 구현하였다.

크루스칼 알고리즘은 부모노드를 찾는 함수(find_parent)와 노드를 서로 연결시키는 함수(union_parent)만 구현하면 해결할 수 있다.

코드는 다음과 같다.

import sys, heapq

def calculate(x1, y1, x2, y2):
    return ((x1-x2) ** 2 + (y1-y2) ** 2) ** (0.5)

def find_parent(start):
    if start != parent[start]:
        return find_parent(parent[start])
    return parent[start]

def union_parent(star1, star2):
    star1 = find_parent(star1)
    star2 = find_parent(star2)
    if star1 < star2:
        parent[star2] = star1
    else:
        parent[star1] = star2

n = int(input())
stars = []
for _ in range(n):
    x, y = map(float, input().split())
    stars.append((x, y))

parent = [i for i in range(n)]
costs = []
answer = 0
for i in range(n-1):
    for j in range(i+1, n):
        heapq.heappush(costs, (calculate(stars[i][0], stars[i][1], stars[j][0], stars[j][1]), i, j))

while costs:
    cost, i, j = heapq.heappop(costs)
    if find_parent(i) != find_parent(j):
        union_parent(i, j)
        answer += cost
print(round(answer, 2))

MST를 만드는 알고리즘으로 프림(Prim)알고리즘이 있다.

프림은 정점 위주의 알고리즘, 크루스칼은 간선 위주의 알고리즘인데, 이 문제의 경우 간선이 아닌 정점(좌표)이 주어졌기 때문에 프림(Prim)알고리즘을 사용하는 것이 더 올바른 방법인 것 같다.
※ 결론 : 프림(Prim)알고리즘 공부하자 😊


profile
허브

0개의 댓글