문제 (https://www.acmicpc.net/problem/4386)
4386번: 별자리 만들기
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일
www.acmicpc.net
최소 비용으로 모든 점을 연결하는 MST 알고리즘을 사용한 문제이다. Union-find를 사용하는 크루스칼 알고리즘으로 문제를 해결했다.
이 문제에서는 점 사이의 거리가 주어지지 않고 별의 좌표가 각각 주어지기 때문에 주어진 좌표들로 점 사이의 거리를 구해주었다. (Line 50~61)
위에서 구한 점 사이의 거리들을 바탕으로 최소 스패닝 트리를 구한다.
[소스코드]
'ALGORITHM > BOJ' 카테고리의 다른 글
| [BOJ] 1939번 중량제한 (C++) (0) | 2022.01.05 |
|---|---|
| [BOJ] 3020번 개똥벌레 (C++) (0) | 2022.01.05 |
| [BOJ] 11779번 최소비용 구하기 2 (C++) (0) | 2022.01.04 |
| [BOJ] 1484번 다이어트 (C++) (0) | 2022.01.03 |
| [BOJ] 1644번 소수의 연속합 (C++) (0) | 2022.01.03 |