[Java] 백준 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보다 작거나 같은 데이터만 입력으로 주어진다.

출력

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

 

 

 

---

 

 

접근 방법

크루스칼 알고리즘을 이용해 풀었다.

 

크루스칼 알고리즘은 모든 간선을 검사는데 해당 간선에 연결된 노드가 각각 다른 그룹일 때만 연결해주는 알고리즘이다.

(두 노드 모두 같은 그룹에 속한다는 것은 이미 연결이 되었다는 것이다.)

 

같은 그룹인지 판단하기 위해서는 해당 노드의 부모를 찾아야하며 이는 재귀 함수로 구현했다. 가장 상위에 있는 부모 노드는 자신의 번호와 부모의 번호가 같기 때문에, 이 조건에 해당되면 해당 번호를 리턴한다. 

 

노드 v1 의 부모와 노드v2의 부모가 다르면 v2의 부모를 v1으로 지정해주었다.

 

 

@참고

입력받은 정보를 Pair 객체에 저장했는데 edge가 최소인 것 부터 먼저 검사해야 하므로 정렬해주어야 한다.

import java.util.*;

class Pair{
	Integer first, second, edge;
	
	public Pair(Integer f, Integer s, Integer e) {
		this.first = f;
		this.second = s;
		this.edge = e;
	}
	public Integer getFirst() {
		return first;
	}
	public Integer getSecond() {
		return second;
	}
	public Integer getEdge() {
		return edge;
	}
}

class Cmp implements Comparator<Pair>{
	@Override
	public int compare(Pair p1, Pair p2) {
		if(p1.getEdge() < p2.getEdge()) return -1;
		else if(p1.getEdge() > p2.getEdge()) return 1;
		else return 0;
	}
}


public class Graph_BOJ1197_최소스패닝트리 {

	static int[] parent = new int[100001];
	

	public static int findParent(int x) {
		if(x==parent[x]) return x;
		else return parent[x] = findParent(parent[x]);
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		ArrayList<Pair> list = new ArrayList<Pair>();
		int[] visited = new int[10001];
		

		int V = sc.nextInt();
		int E = sc.nextInt();
		
		for(int i = 0; i<V; i++) parent[i] = i;
		
		for(int i = 0; i<E; i++) {
			int v1 = sc.nextInt();
			int v2 = sc.nextInt();
			int e = sc.nextInt();
			Pair p = new Pair(v1,v2,e);
			list.add(p);
		}
		
		//첫번째 정렬 방법 
		Collections.sort(list, new Comparator<Pair>() {
			@Override
			public int compare(Pair p1, Pair p2) {
				if(p1.getEdge() < p2.getEdge()) return -1;
				else if(p1.getEdge() > p2.getEdge()) return 1;
				else return 0;
				
			}
		});
		
		//두번째 정렬 방법 
		list.sort(new Cmp());
		
		//세번째 정렬 방법
		Collections.sort(list, new Cmp());
		
		
		

		int sum = 0;

		for(int i = 0; i<list.size(); i++) {
			int v1 = list.get(i).getFirst();
			int v2 = list.get(i).getSecond();
			
	
			//v1부모 = v2부모 -> 이미 연결되어 있는 경우임 -> 스킵
			//부모가 서로 다르면 연결
			int p1 = findParent(v1);
			int p2 = findParent(v2);
			
			if(p1==p2) continue;
			else {
				parent[p2] = p1;
				int e = list.get(i).getEdge();
				sum += e;
			}
		}
		
		System.out.println(sum);
		sc.close();
	}

}