백준 | 1197번. 최소 스패닝 트리 - MST(크루스칼) 문풀

⬛ 백준 1197번. 최소 스패닝 트리 - MST(크루스칼) 문풀

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

1197번: 최소 스패닝 트리

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

---

💚 문제 접근 방식

모든 정점 연결하는 부분 그래프 중 가중치합 최소가 되는 트리 : MST

• MST는 엣지 중심의 알고리즘이고, 무방향 그래프에서 N개 정점 N-1개 간선을 가지며, 사이클도 없지만 단절점도 없는 연결 그래프의 형태를 취하는 신장트리이다.

1. Edge 클래스 선언 (엣지 정보 담는 용도)
2. pQ 활용하여 오름차순으로 입력 간선 정보 (양방향) 처리
3. 양방향이지만 따로 두 정점 잇는 간선 정보는 1개만 있어도 충분하다. (유니온 파인드로 사이클 형성되지 않는 간선에 한해서만 차례대로 추가하므로)
4. 매번 poll한 Edge가 사이클 만들지 않는 경우 union처리 (→ 연결 가중치++, 사용 간선++처리)
5. 이후 사용 간선 N-1개 발생 시, 탈출해서 누적합 해둔 가중치합을 최종 출력하면 된다.

📌 문제에서 가중치가 음수도 가능하고 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력된다고 되어있다.
 즉, int형 범위 안의 가중치만 들어온다는 소리다. 그래서 Edge가 담는 가중치도 int형으로 선언해서 풀었다.

💚 제출 코드

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * 1197번. 최소 스패닝 트리 - MST(크루스칼) 문풀
 * @author MYLG
 *
 */
class Edge implements Comparable<Edge>{
	int s, e, val;
	Edge(int s, int e, int val){
		this.s = s;
		this.e = e;
		this.val = val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}
public class Main {
	static int V, E;
	static int[] parent;
	//find
	static int find(int a) {
		if( a == parent[a]) return a;
		return parent[a] = find(parent[a]);
	}
	
	//union
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a!=b) {
			parent[b] = a;
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		
		V = kb.nextInt();
		E = kb.nextInt();
		//사이클 유무 판단용 
		parent = new int[V+1];
		for(int i=1; i<=V; i++) parent[i]= i;
		
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		
		for(int i=0; i<E; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int v = kb.nextInt();
			pQ.offer(new Edge(a, b, v));
		}
		
		int useEdge = 0;
		int useCost = 0;
		
		while(useEdge < V-1) {
			Edge cur = pQ.poll();
			if(cur == null) break;
			//사이클 형성 안하도록 
			if(find(cur.s) != find(cur.e)) {
				union(cur.s, cur.e); //합치고 
				useCost += cur.val;//가중치 ++ 
				useEdge++;//사용 간선 ++
			}
		}
		System.out.println(useCost);
	}
}