백준 4386 별자리 만들기 파이썬 풀이

난이도 : 골드3

풀이일 : 07097

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

4386번: 별자리 만들기

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import sys

# 연결 확인 함수
def check(m):
    if m != parent[m]:
        parent[m] = check(parent[m])
    return parent[m]

n = int(sys.stdin.readline().strip())
star = []
road = []
result = 0

# 별 정보 추가
for _ in range(n):
    x, y = map(float, sys.stdin.readline().split())
    star.append((x, y))

# 별 사이 거리 추가
for i in range(n-1):
    for j in range(i+1, n):
        road.append((((star[i][0]-star[j][0])**2 + (star[i][1]-star[j][1])**2) ** (1/2), i, j))

road.sort()
parent = [i for i in range(n)]

# 거리가 가까운 순으로 별자리 연결
for i in range(len(road)):
    e, x, y = road[i]
    if x < y:
        x, y = y, x
    if check(x) != check(y):
        parent[check(y)] = check(x)
        result += e

print(round(result, 2))

코드 구성

• check 함수 : 루트 노드를 조사하여 이미 연결되어 있는지 확인
• star : 최초 별의 좌표 저장
• road : 두 별 사이의 간격과 두 별의 star 인덱스 저장
• result : 별자리에 연결된 별들의 거리 합산
• round(float, num) : float을 num 자리수까지 반올림해서 보여줌

# 별 사이 거리 추가
for i in range(n-1):
    for j in range(i+1, n):
        road.append((((star[i][0]-star[j][0])**2 + (star[i][1]-star[j][1])**2) ** (1/2), i, j))

• 이 부분은 제곱근을 구하는 math. 메서드가 있었던 것 같은데 생각나지 않아서 **(1/2)로 제곱근 도출

---

느낀점

한 번에 맞아서 기분 좋다! 내일은 비슷한 유형 더 어려운 문제 풀어야지

이제 이 유형에 익숙해진 것 같기도 하니까 몇 문제만 더 풀고 다음에 풀 수 있도록 남겨둬야지