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)

위에서 구한 점 사이의 거리들을 바탕으로 최소 스패닝 트리를 구한다.


[소스코드]


'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