minimum spanning tree (1) 썸네일형 리스트형 4386 별자리 만들기 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 전형적인 Minimum Spanning Tree 문제이다. 입력으로 별의 x, y 좌표를 받아서 Complete Graph가 되도록 모든 별들 사이의 간선을 만들어준다. 그리고 이제부턴 크루스칼 알고리즘을 적용해서 간선을 정렬해서 최소 비용의 간선부터 루프를 생성하지 않으면 선택하는 식으로 풀면 된다. 간단한 문제였는데, 오랜만에 풀다 보니 사소한 데서 에러가 좀 있었다. 그리고 코드도 좀 더럽게 짠 거 같기도 하고... 꾸준히 풀어야 겠다. C++ 더보기 #in.. 이전 1 다음
