[백준] 1922 : 네트워크 연결 - 최소신장트리(Minimum Spanning Tree, MST) + 크루스칼(Kruskal) JAVA

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

1922번: 네트워크 연결

코드설명

최소신장트리(Minimum Spanning Tree, MST) + 크루스칼(Kruskal) 를 활용하는 문제입니다.

 

크루스칼 알고리즘을 활용하여 최소한의 비용으로 싸이클이 없을 경우를 고려하며 신장 트리를 찾는 문제입니다

.

신장 트리란 그래프 상에서 모든 노드가 사이클 없이 연결된 부분 그래프를 의미합니다.

최소 신장 트리란 그래프 상에서 모든 노드가 사이클 없이 연결된 부분 그래프이면서 모든 정점이 최소 간선의 햡으로 연결된 부분 그래프입니다.

 

이때 최소 신장트리를 찾기 위해 Collections.sort를 간선의 무게에 맞추어서 정렬해줍니다.

싸이클을 판별해내기 위해 유니온파인드(Union-Find)를 통해 판별합니다.

코드

import java.util.*;



public class Main {
	//노드의 개수 (v)와 간선의 개수 (e)
	public static int v, e; 
	public static int[] parent = new int[100001]; //부모테이블 초기화하기
	public static ArrayList<Edge> edges = new ArrayList<>();
	public static int result = 0;
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	v = sc.nextInt();
    	e = sc.nextInt();
    	
    	for(int i=0;i<v;i++) {
    		parent[i] = i;
    	}
    	
    	//모든 간선에 대한 정보를 입력받습니다.
    	for(int i=0;i<e;i++) {
    		int a = sc.nextInt();
    		int b = sc.nextInt();
    		int cost = sc.nextInt();
    		edges.add(new Edge(cost, a, b));
    	}
    	
    	//간선을 비용순으로 정렬합니다
    	Collections.sort(edges);
    	
    	//간선을 하나씩 확인합니다.
    	for(int i=0;i<edges.size();i++) {
    		int cost = edges.get(i).distance;
    		int a = edges.get(i).nodeA;
    		int b = edges.get(i).nodeB;
    		//싸이클이 발생하지 않을경우에만 집합에 포함시킵니다.
    		if( findParent(a) != findParent(b)) {
    			unionParent(a, b);
    			result += cost;
    		}
    	}
    	
    	System.out.println(result);
    	
    }
    
    public static int findParent(int x) {
    	if( x == parent[x]) return x;
    	return parent[x] = findParent(parent[x]);
    }
    
    public static void unionParent(int a, int b) {
    	a = findParent(a);
    	b = findParent(b);
    	if( a < b ) parent[b] = a;
    	else parent[a] = b;
    }
    
}

class Edge implements Comparable<Edge>{
	int distance;
	int nodeA;
	int nodeB;
	
	public Edge(int distance, int nodeA, int nodeB) {
		this.distance = distance;
		this.nodeA = nodeA;
		this.nodeB = nodeB;
	}
	
	@Override
	public int compareTo(Edge other) {
		if(this.distance < other.distance) {
			return -1;
		}
		return 1;
	}
}