백준 별자리 만들기 43861 [백준] 26. 별자리 만들기 4386 해설 별자리 만들기 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 풀이 높은 정답 비율답게 쉽게 풀 수 있었던 문제입니다. 결국에는 최소 비용으로 별자리를 이어주면 되기 때문에 최소 간선만을 이어줘야 되며 사이클이 생기면 안 됩니다. 따라서 최소 신장 트리 알고리즘을 사용하면 되는 문제입니다. 다만 간선이 따로 주어지지 않았기 때문에 각 별자리의 좌표를 이용하여 모든 경우의 간선을 구해주면 됩니다. 먼저 크루스칼을 이용한 풀이입니다. 모든 간선을 구한 뒤 우선순위 큐에 넣어줍니다. 그다음 큐에서 간선을 하나씩.. 2024. 1. 17. 이전 1 다음 반응형
