프로그래밍
-
[백준] 4386번 별자리 만들기(파이썬, MST)Coding Test/Algorithm 2021. 10. 31. 19:06
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 이번 문제는 최소 스패닝 트리 문제였다. kuruskal mst 알고리즘을 사용했다. 핵심은 간선간의 비용은 좌표 간의 거리이며 2차 평면에서 두 좌표의 거리는 직각삼각형을 그려서 빗변의 길이를 구하면 두 좌표간의 거리가 된다. x1, y1 과 x2, y2 두 좌표가 있다면 |x1 - x2|^2 + |y1 - y2|^2 의 루트 값이 바로 두 좌표간의 거리가 된다. import sys import ..