prim
-
[백준 4386 - JAVA] 별자리 만들기Algorithm 2020. 11. 12. 17:52
4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 기본적인 MST (최소스패닝트리) 문제! 나는 입력을 잘 못 받아두고 왜 안되냐고 고통받다가 나중에 발견했다 :( 프림이나 크루스칼 둘 중에 한가지를 사용해서 풀 수 있는데, 나는 프림을 사용해서 풀었다. 크루스칼은 union, findSet을 구현하기가 너무 귀찮았다 =(:з」∠)_ 풀이 방법 입력받은 좌표를 이용해 다른 별과의 거리를 구한다. 첫번째 별부터 시작! 다른 별들의 번호와 첫번째별과의 거리를 Edge 객체로 만들어 PQ에 넣는다. 방문한 별의 개수(..