반응형
1) 크루스칼
간선 중심으로 최소 신장 트리를 구하는 알고리즘
1) 부모를 나 자신으로 셋팅
2) 모든 간선을 입력받을 때 우선순위큐에 넣기
3) 가중치가 적은 간선부터 꺼내 시작노드와 끝노드의 부모가 같지 않다면 Union해주고, 채택
4) 우선순위큐가 empty 상태가 되면 모든 간선을 본 것이기 때문에 끝이다. (그래서 간선의 수가 적을수록 유리하다)
import java.util.*;
import java.io.*;
//크루스칼
class Main {
static PriorityQueue<Edge> pq;
static int V, E;
static int[] p;
static int[] order;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String VE = br.readLine();
StringTokenizer st = new StringTokenizer(VE," ");
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
pq = new PriorityQueue<>();
for(int i=0; i<E; i++){
String ABC = br.readLine();
st = new StringTokenizer(ABC," ");
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
pq.offer(new Edge(A, B, C));
}
//입력 끝
//1. 부모를 나 자신으로 설정
p = new int[V+1];
order = new int[V+1];
SetP();
//2. MST 연결
int len = MST();
System.out.println(len);
}
public static int MST(){
int len = 0;
while(!pq.isEmpty()){
Edge cur = pq.poll();
int from = cur.from;
int to = cur.to;
if(Find(from) == Find(to)) continue;
Union(from, to);
len += cur.len;
}
return len;
}
public static void SetP(){
for(int i=1; i<V+1; i++){
p[i] = i;
}
}
public static int Find(int child){
if(p[child] == child) return child;
return p[child] = Find(p[child]);
}
public static void Union(int c1, int c2){
int p1 = p[c1];
int p2 = p[c2];
if(order[p1]>= order[p2]){
p[p2] = p1;
order[p1]++;
}else{
p[p1] = p2;
order[p2]++;
}
}
public static class Edge implements Comparable<Edge>{
int from;
int to;
int len;
public Edge(int from, int to, int len){
this.from = from;
this.to = to;
this.len = len;
}
@Override
public int compareTo(Edge o){
return this.len>o.len?1:-1;
}
}
}
시간복잡도 : O(n^2log n)
2) 프림
정점 중심으로 최소 신장 트리를 구하는 알고리즘
V개의 정점을 모두 잇기 위해선 최소 V-1개의 간선이 필요하다.
시작점과 연결된 모든 노드를 우선순위 큐에 담아두고, 가중치가 작은 정점부터 꺼내서 MST를 구성한다.
V-1개의 간선이 모두 채택될 때까지 하나의 정점을 우선순위큐에서 빼고, 주변 노드들을 모두 넣는 것을 반복한다. (그래서 노드의 수가 작을수록 유리하다.)
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static List<Node>[] EdgeList;
static int E,V;
static int result;
static class Node implements Comparable<Node>{
int endNode;
int weight;
public Node(int endNode, int weight) {
this.endNode = endNode;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return this.weight>o.weight?1:-1;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
V = sc.nextInt();//정점의 개수
E = sc.nextInt();//간선의 개수
EdgeList = new ArrayList[V+1];//1번부터 시작
for(int i=0;i<V+1;i++) {
EdgeList[i] = new ArrayList<>();
}
//간선 정보 받기
for(int i=0;i<E;i++) {
int A = sc.nextInt();
int B = sc.nextInt();
int w = sc.nextInt();
//무향그래프
EdgeList[A].add(new Edge(B,w));
EdgeList[B].add(new Edge(A,w));
}
//정보 입력 모두 받음
//구현
prim(1);
//결과 출력
System.out.println(result);
}
static public void prim(int startNode) {
Queue<Node> pq = new PriorityQueue<>();
boolean[] visited = new boolean[V+1];//1번부터 시작
int pick=0;
visited[startNode]=true;
pq.addAll(EdgeList[startNode]);
while(pick!=V-1) {
Edge curr = pq.poll();
if(!visited[curr.endNode]) {
result+=curr.weight;//간선 선택완료
pick++;
visited[curr.endNode]=true;
pq.addAll(EdgeList[curr.endNode]);
}
}
}
}
시간복잡도 : O(n^2log n)
코딩테스트 보기 전 이게 웬 벼락치기람
MST 하도 안풀어서 까먹어가지고 불안해서 한 번 돌아보았다.
반응형
