원더랜드 (최소스패닝트리)

* 크루스칼

 

최소 스패닝 트리의 특성,

1. 회로가 없다. (연결되면 그래프가 된다)

- 회로의 구성여부는 Union & Find로 판단한다.

2. Vertex의 수 -1 == Edge의 수

- 시간복잡도 줄일 경우 사용.

 

 

 

전략,

입력된 정점 정보를 cost기준으로 오름차순 정렬 이후, Union이 아닌 경우 선택한다. 

(cost가 작은 녀석부터 Union이 된다 => 최소 비용)

 

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

//원더랜드
//간선을 오름차순 정렬
class Main {

	static int m, n, answer;

	static int[] unf;
	public static int Find(int v) {
		if (v == unf[v]) return v;
		else return unf[v]=Find(unf[v]);
	}
	
	public static void Union ( int a , int b) {
		int fa = Find(a);
		int fb = Find(b);
		if( fa != fb)  unf[fa]=fb;		
	}
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		//도시 개수
		n = in.nextInt();
		//간선개수
		m = in.nextInt();
		ArrayList<Edge> arr = new ArrayList<>();
		unf = new int [n+1];
		
		//유니온 초기화 (자기 자신의 값)
		for (int i = 1 ; i <= n ; i++ ) unf[i] = i;
		for (int i =0 ;  i < m; i++) {
				int a = in.nextInt();
				int b = in.nextInt();
				int c = in.nextInt();
				arr.add( M.new Edge(a, b, c));
		}
		
		//cost에 대해 오름차순 정렬
		Collections.sort(arr);
		
		//회로가 아닌 것만 누적하며 선택
		for ( Edge ob : arr) {
			int fv1 = Find(ob.v1);
			int fv2 = Find(ob.v2);
			

			//서로소 관계일 경우 누적
			if (fv1 != fv2) {
				answer += ob.cost;
				Union(fv1, fv2);
			}
			
		}
		
		System.out.println(answer);
		

	}
	class Edge implements Comparable<Edge>{
		
		int v1;
		int v2;
		int cost;
		Edge( int v1, int v2, int cost){
			this.v1 = v1;
			this.v2 = v2;
			this.cost = cost;
			
		}
		@Override
		public int compareTo(Main.Edge o) {
			return this.cost - o.cost;
		}		
	}
}
ex)
input
9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15
output
196

 

 

 

* Prim 

 

우선순위 큐 사용.

1. 0번 정점에서 출발하는 것으로 가정 => pQ.offer( new Edge(1,0) );

2. 방문하는 vex의 ch리스트를 통해 회로를 차단.

3. 인접 리스트에서 현재 vex의 간선을 pQ에 모두 넣어준다. 

4. pQ에서 가장 cost가 작은 간선을 선택한다 (Greedy 기법) 

5. 결국 cost가 큰 간선들은 모두 버려진다.

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

//원더랜드
class Main {

	static int m, n, answer;


	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		//도시 개수
		n = in.nextInt();
		//간선개수
		m = in.nextInt();
		
		ArrayList<ArrayList<Edge>> graph = new ArrayList<ArrayList<Edge>>();
		
		for ( int i = 0 ; i <=n; i++) {
			graph.add( new ArrayList<Edge>());
		}
		
		//방문 체크를 위한 배열
		int [] ch = new int[n+1];
		for (int i= 0; i < m ; ++i ) {
			int a = in.nextInt();
			int b = in.nextInt();
			int c = in.nextInt();
			
			//무방향성 그래프의 인접리스트 생성
			graph.get(a).add(M.new Edge(b, c));
			graph.get(b).add(M.new Edge(a, c));
		}

		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		
		//초기 값을 0번 노드에서 cost 0으로 간주
		pQ.offer(M.new Edge(1, 0));
		
		while(!pQ.isEmpty()) {
			Edge tmp = pQ.poll();
			
			//end vertex
			int ev = tmp.vex;
			if( ch[ev] == 0 ) {
				ch[ev] = 1;
				//비용 누적
				answer += tmp.cost;
				//ev의 인접 리스트를 탐색하여 방문하지 않은 정점을 offer
				for (Edge ob : graph.get(ev)) {
					//이미 선택된 정점은 계산하지 않음.
					if(ch[ob.vex] == 0)  
						pQ.offer(M.new Edge(ob.vex, ob.cost));					
				}
			}
		}
		

		System.out.println(answer);
		

	}
	class Edge implements Comparable<Edge>{
		
		int vex;
		int cost;
		Edge( int vex, int cost){
			this.vex = vex;
			this.cost = cost;			
		}
		@Override
		public int compareTo(Main.Edge o) {
			return this.cost - o.cost;
		}		
	}
}

ex)
input
9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15
output
196