ALGORITHM/BOJ
[BOJ] 4386번 별자리 만들기 (C++)
yegyeom
2022. 1. 4. 01:05
문제 (https://www.acmicpc.net/problem/4386)
4386번: 별자리 만들기
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일
www.acmicpc.net
최소 비용으로 모든 점을 연결하는 MST 알고리즘을 사용한 문제이다. Union-find를 사용하는 크루스칼 알고리즘으로 문제를 해결했다.
이 문제에서는 점 사이의 거리가 주어지지 않고 별의 좌표가 각각 주어지기 때문에 주어진 좌표들로 점 사이의 거리를 구해주었다. (Line 50~61)
위에서 구한 점 사이의 거리들을 바탕으로 최소 스패닝 트리를 구한다.
[소스코드]
