문제

https://www.acmicpc.net/problem/4386
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

---

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

---

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

---

풀이

접근방법

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
  라는 문제 조건을 읽어보면 MST를 완성시키라는 말임을 알 수 있다.

다만, 조금 더 번거로운 작업은 각 점 사이의 거리를 계산해야한다.
또한 오차를 고려해서 문제를 풀어야 한다.

각 점의 수가 충분히 작기 때문에 모든 점의 거리를 계산하여 진행했다.

( MST란? : https://velog.io/@hyeokkr/%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%ACMST-Minimal-Spanning-Tree )

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
	static int N;
	static List<Node>[] list;
	static boolean[] visit;

	static class Node implements Comparable<Node> {
		int to;
		int weight;

		@Override
		public int compareTo(Node o) {
			return this.weight - o.weight;
		}

		Node(int b, int c) {
			to = b;
			weight = c;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = stoi(in.readLine());
		visit = new boolean[N];
		list = new List[N];
		for (int i = 0; i < N; ++i)
			list[i] = new ArrayList<>();

		for (int i = 0; i < N; ++i) {
			String[] splitedLine = in.readLine().split(" ");
			for (int j = 0; j < N; ++j) {
				int value = stoi(splitedLine[j]);
				if (value != 0)
					list[i].add(new Node(j, value));
			}
		}

		PriorityQueue<Node> pq = new PriorityQueue<>();

		long result = 0;
		int count = 0;
		pq.add(new Node(0, 0));
		while (!pq.isEmpty()) {
			Node cur = pq.poll();
			if (visit[cur.to])
				continue;

			visit[cur.to] = true;
			result += cur.weight;
			for (Node node : list[cur.to])
				pq.add(node);
			count++;
			if (count == N)
				break;
		}
		System.out.println(result);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}

}