크루스칼
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Edge implements Comparable<Edge>{
public int v1; // 정점 1
public int v2; // 정점 2
public int cost; // 두 정점을 연결하는 비용
Edge(int v1, int v2, int cost){
this.v1 = v1;
this.v2 = v2;
this.cost = cost;
}
@Override
public int compareTo(Edge ob){
return this.cost - ob.cost; // cost 오름차순 정렬
}
}
class Main{
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) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 정점 개수
int m = sc.nextInt(); // 간선 개수
unf = new int[n+1];
ArrayList<Edge> arr = new ArrayList<>();
for(int i=1; i<=n; i++) unf[i] = i;
for(int i=0; i<m; i++){
// a도시와 b도시를 연결하는 비용 c
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
arr.add(new Edge(a, b, c));
}
int answer = 0;
Collections.sort(arr);
for(Edge ob : arr){
int fv1 = Find(ob.v1);
int fv2 = Find(ob.v2);
if(fv1 != fv2){ // 다른 집합이라면
answer += ob.cost; // 비용 누적
Union(ob.v1, ob.v2); // 하나의 집합으로 합치기
}
}
System.out.println(answer);
}
}
프림
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
class Edge implements Comparable<Edge>{
public int vex; // 정점
public int cost; // 점점으로 가는데 드는 비용
public Edge(int vex, int cost) {
this.vex = vex;
this.cost = cost;
}
@Override
public int compareTo(Edge ob){
return this.cost - ob.cost; // cost 오름차순 정렬
}
}
class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 정점 개수
int m = sc.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 = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
// 무방향 그래프
graph.get(a).add(new Edge(b,c)); // a 정점에서 b 정점으로 가는데 드는 비용 c
graph.get(b).add(new Edge(a, c)); // b 정점에서 a 정점으로 가는데 드는 비용 c
}
int answer = 0;
PriorityQueue<Edge> pq = new PriorityQueue<>(); // 최솟값 비용을 먼저 우선순위로
pq.offer(new Edge(1, 0)); // 정점 1부터 넣음
while(!pq.isEmpty()){
Edge tmp = pq.poll(); // 비용이 가장 작은 것을 꺼냄
int ev = tmp.vex; // 도착 정점
if(ch[ev] == 0){ // 방문하지 않았다면
ch[ev] = 1; // 방문 체크
answer+=tmp.cost; // 비용 누적
for(Edge ob : graph.get(ev)){ // ev와 연결된 정점들 탐색
if(ch[ob.vex] == 0) pq.offer(new Edge(ob.vex, ob.cost)); // 방문하지 않은 정점이라면 큐에 넣음
}
}
}
System.out.println(answer);
}
}
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 10974- 모든 순열 (0) | 2022.11.29 |
---|---|
[JAVA] 백준 2583- 영역 구하기 (0) | 2022.11.27 |
[JAVA] 알고리즘 : 그리디- 친구인가? (Disjoint-Set : Union&Find) (0) | 2022.11.25 |
[JAVA] 알고리즘 : 그리디- 다익스트라 알고리즘 (0) | 2022.11.25 |
[JAVA] 백준 13458- 시험 감독 (0) | 2022.11.25 |