728x90
난이도 : 골드3
풀이일 : 07097
https://www.acmicpc.net/problem/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)로 제곱근 도출
느낀점
한 번에 맞아서 기분 좋다! 내일은 비슷한 유형 더 어려운 문제 풀어야지
이제 이 유형에 익숙해진 것 같기도 하니까 몇 문제만 더 풀고 다음에 풀 수 있도록 남겨둬야지
'알고리즘 > 🥇 골드' 카테고리의 다른 글
백준 1717 집합의 표현 파이썬 풀이 (1) | 2024.01.14 |
---|---|
백준 1111 IQ Test 파이썬 풀이 (0) | 2023.07.21 |
백준 13418 학교 탐방하기 파이썬 풀이, 반례 (0) | 2023.07.08 |
백준 1197 최소 스패닝 트리 파이썬 풀이 (0) | 2023.07.07 |
백준 2146 다리 만들기 파이썬 풀이 (0) | 2023.07.05 |