ConnectingIsland.java

public class ConnectingIsland {

	static class Edge implements Comparable<Edge> {
		int from;
		int to;
		int cost;
		public Edge(int from, int to, int cost) {
			super();
			this.from = from;
			this.to = to;
			this.cost = cost;
		}
		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.cost, o.cost);
		}
	}
	
	private static int findSet(int[] p, int x) { // 최상위 부모를 찾아 반환하는 함수
		if (p[x] == x) return x;
		else return p[x]=findSet(p, p[x]); // x의 최상위 부모를 찾아서 반환한다.
	}
	private static void union(int[] p, int x, int y) { // 최상위 부모를 비교해 연결하는 함수
		if (x < y) p[findSet(p, y)] = findSet(p, x); // x의 최상위 부모를 y의 최상위 부모로 한다.
		else p[findSet(p, x)] = findSet(p, y); // y의 최상위 부모를 x의 최상위 부모로 한다.
	}
	
	private static PriorityQueue<Edge> pq;
	public int solution(int n, int[][] costs) {
		int[] p = new int[n];
		pq = new PriorityQueue<Edge>();
		
		// 최상위 부모를 자기 자신으로 초기화
		for (int i = 0; i < p.length; i++) p[i] = i;
		
		// 우선순위 큐에 집어넣어 간선 비용을 오름차순으로 저장
		int from,to,cost;
		for (int i = 0; i < costs.length; i++) {
			from = costs[i][0];
			to = costs[i][1];
			cost = costs[i][2];
			pq.add(new Edge(from, to, cost));
		}
		
		int res = 0, cnt = 0;
		while(!pq.isEmpty()) {
			Edge curr = pq.poll();
			
			// 사이클이 만들어지는 지 확인
			if (findSet(p,curr.from) != findSet(p,curr.to)) { // 사이클을 만들어내지 않으면
				res += curr.cost;
				if (++cnt==n) break;
				union(p,curr.from,curr.to); // 두 섬의 부모를 찾아 연결한다.
			}
		}
		System.out.println(res);
		return res;
    }
	public static void main(String[] args) {
		int[][] costs = new int[][] {{0,1,7},{3,0,4},{1,2,1},{1,3,1},{2,3,3},{1,4,4},{4,0,3},{3,4,2}};
		int n = 5;
		new ConnectingIsland().solution(n, costs);
	}

}