본문으로 건너뛰기

4386 - 별자리 만들기

정보
  • 문제 보기: 4386 - 별자리 만들기
  • 소요 시간: 16분 45초
  • 풀이 언어: python
  • 체감 난이도: 2️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

그래프 최소스패닝트리 유니온파인드


풀이 코드​

정보
  • 메모리: 35560 KB
  • 시간: 36 ms
import sys
from math import sqrt
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

parent = []
def union(a, b):
    global parent
    
    pa = find(a)
    pb = find(b)
    
    if pa < pb:
        parent[pb] = pa
    else:
        parent[pa] = pb

def find(x):
    global parent
    
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]
    
def calc_dist(s1, s2):
    return sqrt((s1[0]-s2[0]) ** 2 + (s1[1]-s2[1]) ** 2)

def solution():
    global parent
    n = int(input())
    parent = [i for i in range(n)]
    star = []
    graph = []
    for _ in range(n):
        x, y = map(float, input().split())
        star.append((x, y))
    
    # create star graph
    for i in range(n):
        for j in range(i+1, n):
            weight = calc_dist(star[i], star[j])
            graph.append((weight, i, j))
            
    # Kruskal
    ans = 0
    graph.sort()
    for data in graph:
        weight, a, b = data
        if find(a) != find(b):
            ans += weight
            union(a, b)
    
    print("{:.2f}".format(ans))


if __name__ == '__main__':
    solution()

풀이 해설​

MST 문제이므로, 크루스칼 알고리즘을 사용하면 된다.

Kruskal 알고리즘의 설명은
최소 스패닝 트리 풀이 내용으로 대체한다.

📚Reference​

프림 알고리즘이 크루스칼보다 나은 상황이 있나요?
TL;DR

앵간하면 PS 풀다가 굳이 크루스칼 냅두고 프림 쓸 일이 잘 없다.


📌별과 별 사이 거리 계산하기​

def calc_dist(s1, s2):
    return sqrt((s1[0]-s2[0]) ** 2 + (s1[1]-s2[1]) ** 2)

(x1−x2)2+(y1−y2)2\sqrt{(x1-x2)^2 + (y1-y2)^2}

점과 점 사이 거리 공식을 그대로 적용한다.


📌그래프 생성하기​

크루스칼을 수행하기 전, 모든 별들을 연결한 그래프가 필요하다.

# create star graph
for i in range(n):
    for j in range(i+1, n):
        weight = calc_dist(star[i], star[j])
        graph.append((weight, i, j))

따라서 기본 MST 문제와의 차이점이라면, O(N2)O(N^2)으로 그래프를 먼저 생성하는 과정이 하나 추가되는 문제이다.


메모​

# 소수 둘째 자리까지 출력
print("{:.2f}".format(ans))
  • 파이썬 포맷 출력 순간 기억이 안났음
    • 허접
채점현황
  • 이 문제는 깔끔하게 원트컷 성공~