[백준] 1647: 도시 분할 계획 - 최소신장트리(Minimum Spanning Tree, MST) + 크루스칼(Kruskal) JAVA

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

1647번: 도시 분할 계획

코드설명

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

 

크루스칼 알고리즘을 활용하여 최소한의 비용으로 신장 트리를 찾는 문제입니다

.

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

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

 

최소 신장트리 내에 포함된 간선 중에서 가장 비용이 큰 간선은 Collections.sort에 의해 마지막 간선이므로 해당 간선을 마지막에 업데이트한 값이 가장 비용이 큰 간선입니다.

(최소 신장트리 내의 모든 비용) -  (가장 비용이 큰 간선) = (2개로 나눈것 중에서 최소의 값) 

이 성립합니다.

코드

import java.util.*;



public class Main {
	
	public static int N,M;
	public static int[] parent = new int[1000001];
	public static ArrayList<Edge> edges = new ArrayList<>();
	public static int result = 0;
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N=sc.nextInt();
    	M=sc.nextInt();
    	
    	//부모테이블 상에서 부모를 자기자신으로 초기화합니다.
    	for(int i=0;i<N;i++) {
    		parent[i] = i; 
    	}
    	
    	//모든 간선에 대한 정보를 입력받습니다.
    	for(int i=0;i<M;i++) {
    		int a = sc.nextInt();
    		int b = sc.nextInt();
    		int cost = sc.nextInt();
    		edges.add(new Edge(a, b, cost));
    	}
    	
    	Collections.sort(edges);
    	
    	//최소 신장 트리에 포함되는 간선 중에서 가장 비용이 큰 간선
    	int last = 0; 
    	
    	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;
    			last = cost;
    		}
    	}
    	System.out.println(result - last);
    	
    }
    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 nodeA, int nodeB, int distance) {
		this.nodeA = nodeA;
		this.nodeB = nodeB;
		this.distance = distance;
	}
	
	//길 유지비가 짧은것이 우선순위를 가지도록 합니다.
	@Override
	public int compareTo(Edge other) {
		if(this.distance > other.distance) {
			return 1;
		}else if(this.distance < other.distance){
			return -1;
		}
		else return 0;
	}
}