[BOJ] 4386. 별자리 만들기

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

4386번: 별자리 만들기

 

 

1. 해결방법

"""
1. 아이디어
- MST 이용
- 입력하는 2차원 배열 x, y를 입력
- 별들 사이의 거리를 계산후에 star_dis 리스트에 append
- heap에 초기값 [0, 1]을 저장
- heap이 빌때까지 반복
    - 힙의 최소값을 pop후에 해당 별 좌표의 방문 여부를 체크
    - result에 비용 추가
    - 방문하지 않았다면 방문 체크하고 해당 별의 좌표가 포함된 인접리스트를 for문으로 가져온다.
    - 인접리스트의 별 좌표를 heap을 push

2. 시간복잡도
- O(NlogN)
"""

 

 

2. 정답코드

import sys
import heapq
import math
input = sys.stdin.readline

# input
n = int(input())

edge = [[] for _ in range(n + 1)]
star_dis = [[] for _ in range(n + 1)]

for i in range(1, n + 1):
    x, y = map(float, input().split())
    edge[i].append([x, y])


# 별 거리
for i in range(1, n + 1):
    for j in range(i, n + 1):

        if i == j:
            continue
        dis = round(math.sqrt(
            (abs(edge[i][0][0] - edge[j][0][0]))**2 + (abs(edge[i][0][1] - edge[j][0][1]))**2
        ), 2)

        star_dis[i].append([dis, j])
        star_dis[j].append([dis, i])

# heap
heap = [[0, 1]]
result = 0
chk = [False] * (n + 1)

while heap:
    w, each_node = heapq.heappop(heap)

    if chk[each_node] == False:
        chk[each_node] = True
        result += w

        for next_node in star_dis[each_node]:
            if chk[next_node[1]] == False:
                heapq.heappush(heap, next_node)

print(result)

MST prim알고리즘으로 해결하였고, MST의 기본적인 문제에서 초반 도입 부분을 살짝 꼬아놓은 문제이다.
기본 문제에서는 비용이 바로 나와있었지만, 이 문제에서는 별들 사이의 거리를 math와 round 함수를 사용해서 나타내고 i, j 위치에 맞게 리스트에 append 해야한다.
그 뒤로는 일반 mst 문제와 같다.