* 크루스칼
최소 스패닝 트리의 특성,
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
