백준 1922 - 네트워크 연결(자바 구현)

public class Q_1922 {

	static class Edge {
		private int[] node = new int[2];
		private int distance;
		
		public Edge(int a, int b, int distance) {
			node[0] = a;
			node[1] = b;
			this.distance = distance;
		}

		public int getDistance() {
			return distance;
		}

		public void setDistance(int distance) {
			this.distance = distance;
		}

		public int[] getNode() {
			return node;
		}

		public void setNode(int[] node) {
			this.node = node;
		}
		
	}

	static int getParent(int[] parent, int a) {
		if(parent[a] == a) return a;
		return parent[a] = getParent(parent, parent[a]); 
	}
	
	static void union(int[] parent, int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		
		if(a < b) parent[b] = a;
		else parent[a] = b;
	}
	
	static boolean parentCompare(int[] parent, int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		
		if(a == b) return true;
		else return false;
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int nodeCount = Integer.parseInt(br.readLine());
		int edgeCount = Integer.parseInt(br.readLine());
		
		int[] parent = new int[nodeCount+1];
		List<Edge> list = new ArrayList<>();

		//초기 부모노드 초기화
		for (int i = 1; i < nodeCount+1; i++) {
			parent[i] = i;
		}
		
		for (int i = 0; i < edgeCount; i++) {
			String nodeInfo = br.readLine();
			String[] nodeInfoArr = nodeInfo.split(" ");
			list.add(new Edge(Integer.parseInt(nodeInfoArr[0]), Integer.parseInt(nodeInfoArr[1]), Integer.parseInt(nodeInfoArr[2])));
		}
		
		Collections.sort(list, 
				(a, b) -> a.getDistance()-b.getDistance()
		);

		int sum = 0;		
		for (int i = 0; i < list.size(); i++) {
			if (!parentCompare(parent, list.get(i).getNode()[0], list.get(i).getNode()[1])) {
				sum += list.get(i).getDistance();
				union(parent, list.get(i).getNode()[0], list.get(i).getNode()[1]);
			}
		}
		System.out.print(sum);
	}
}

 

URL :  https://www.acmicpc.net/problem/1922