[자바] 백준 1197 - 최소 스패닝 트리

최소 스패닝 트리(MST) 문제는 보통 크루스칼이나 프림 알고리즘으로 해결할 수 있다고 한다. 

 

- 크루스칼 : 간선 위주로 생각. 가중치가 가장 낮은 간선을 선택하거나 가중치가 가장 큰 간선을 제거하는 방향으로 로직을 구현한다.

     · 시간복잡도는 간선이 e개 있을 때  O(elog₂e)  

- 프림 : 노드 위주로 생각. 노드 하나를 선택하여 그 노드와 연결된 간선 중 가중치가 가장 작은 간선을 선택해가는 방향으로 로직을 구현한다.

     · 시간복잡도는 노드가 n개 있을 때  O(n^2)

  

둘 다 공통적인 건, 사이클이 생기면 안 되기 때문에 유니온-파인드 알고리즘을 알고 있어야 한다는 것.

 

---

이 문제는 가중치가 낮은 간선을 선택해가는 방식으로 풀었다. 

방법 1. 각 간선들을 ArrayList에 담아서 Collections.sort를 한 다음에 for-each를 통해 간선 선택하는 방법

방법 2. 각 간선들을 PriorityQueue에 담아서 while문으로 모든 간선들을 체크하는 방법 

 

작년에는 방법 1로 풀었고, 이번에는 방법 2로 풀었는데 미세하게 방법 1이 속도가 빠르다.

/* 2021.01.05(화) */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
	
	static int[] parent;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().trim().split(" ");
		int V = Integer.parseInt(str[0]);
		int E = Integer.parseInt(str[1]);
		int total = 0;
		
		parent = new int[V+1];
		for(int i=0;i<=V;i++) parent[i] = i;
		
		
		int start = 0, end = 0, weight = 0;
		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		for(int i=0;i<E;i++) {
			str = br.readLine().trim().split(" ");
			
			start 	= Integer.parseInt(str[0]);
			end 	= Integer.parseInt(str[1]);
			weight 	= Integer.parseInt(str[2]);
			
			pq.offer(new Edge(start, end, weight));
		}
		
		Edge currEdge;
		while(!pq.isEmpty()) {
			currEdge = pq.poll();
			
			//시작 노드와 끝 노드의 부모가 같다면 해당 간선을 선택해서 경로를 만들었을 때, 
			//사이클이 생성되어 버린다. 
			//--> 부모가 같다면 간선을 선택하지 않고 그냥 넘어간다.
			if(hasSameParent(currEdge.s, currEdge.e)) continue;
			
			//사이클이 생성되지 않는 경우라면, 해당 간선을 선택한다.
			//--> s와 e의 부모를 합쳐주고, 가중치를 total 변수에 더해준다. 
			union(currEdge.s, currEdge.e);
			total += currEdge.w;
		}
		
		System.out.println(total);
	}
	
	private static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		//작은 숫자의 parent로 통일시켜주기로 했으니까,
		//최종적으로 노드들은 parent가 전부 1일 것
		//(1부터 V까지 모두 연결시켜야 하니까!)
		if(x>y) parent[x] = y;
		else parent[y] = x;
	}

	private static boolean hasSameParent(int s, int e) {
		int sParent = find(s);
		int eParent = find(e);
		
		if(sParent==eParent) return true;
		else return false;
	}

	private static int find(int x) {
		
		if(parent[x]==x) return x;
		return parent[x] = find(parent[x]);
	}

	static class Edge implements Comparable<Edge>{
		
		int s;
		int e;
		int w;
		
		public Edge(int s, int e, int w) {
			this.s = s;
			this.e = e;
			this.w = w;
		}
		
		@Override
		public int compareTo(Edge o) {
			return this.w-o.w;
		}
	}
}