[알고리즘]최소신장트리(크루스칼,프림)

이름부터 무슨 중국말도 아니고 신장트리래. 영어는 더 어려움 수학공식같은 이름..

그러나 막상해보면 별거아님 또. 이름 지은 사람들 다들 한대씩 맞아야함.ㅋㅋ

 

위 알고리즘을 쓰는 때는, 그래프에서 최소비용을 구할 때 쓰인다. 모든 정점을 연결하는 간선들의 가중치의 합이 최소가되는 것을 구할 때 쓰인다.

 

신장트리란, 위구르신장지역 아님. 아니 암튼, 신장트리란 n개의 정점으로 이뤄진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이뤄진 트리를 말함. 걍 간단하게 말하면 모든 정점에 딱 하나씩만 간선이 있는거임.

이때 최소신장트리란,

무향 가중치 그래프에서 신장트리를 구성하는 가중치의 합이 최소인 신장트리를 말함. 그니까 두 정점 사이에 간선이 여러개 있을 수 있는데 그중 가장 쬐그만 간선들로 이뤄진 신장트리임.

 

그래프의 간선 가중치를 묻는 질문에서, 입력값이 간선으로 주어지기도 하고, 정점으로 주어지기도 한다.

간선으로 주어지면 크루스칼을 쓰고, 정점으로 주어지면 프림을 쓰면 된다.

정점에 비해 간선이 너무 많으면 크루스칼 못씀.(완전그래프라면 N개 정점은 최대 N-1개의 간선있을 수 있음. 그럼 (N-1)^2개나 되는데, 10000개면 약 1억개임. 근데 이 간선을 정렬하면 NlogN..이거 거의 불가능함. 이럴 땐 프림을 써야 한다)

 

먼저 크루스칼을 보자.

크루스칼

크루스칼은 나름 직관적으로 이해가 된다.

 

이때 먼저 알아야 할 것이 있다. 집합관련 함수를 구현하는 것이다.

키포인트:

1. makeSet()을 통해 나 자신이 나의 부모가 되는 단위집합을 생성하는 것

2. findSet()에서 재귀를 통해 나의 root부모를 찾는것. 특히 찾는과정에서 부모,증부모의 부모 모두 다 root부모로 바꿔치기됨. 또한, 결국 findSet이란 건 집합을 찾는게 아니라, 대표자(=루트부모)를 찾아주는것임.

3. union()으로 두 집합(=두 수가 속해있는 집합)을 합치는데, 이건 결국 두개의 루트부모를 찾아서 하나를 나머지 하나의 부모로 만들어주는 작업임

4. Edge함수는 from, to는 물론이고 weight가 추가되었다. 또한 정렬을 위해 Comparable을 상속하고 compareTo를 오버라이드한다.

5. 103번라인에서 오름차순 정렬을한다. 이는 weight가 가장 조그만 애부터 하나씩 선을 연결해줘야 하기 때문이다.

6. 조그마한 간선부터 하나씩 서로 from과 to가 같은 집합인지 확인하면서, 서로 다른애면 하나로 합쳐주면서 총 N-1개가 되면 신장트리가 완성되므로 끝내준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/*
 * 
5 10
0 1 5
0 2 10
0 3 8
0 4 7
1 2 5
1 3 3
1 4 6
2 3 1
2 4 3
3 4 1

output==>10

7 11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51

output==>175
 */
public class MST1_KruskalTest{
	
	static class Edge  implements Comparable<Edge>{
		int from, to, weight;

		public Edge(int from, int to, int weight) {
			super();
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return this.weight - o.weight;
		}
	}
	
	static int N;
	static int[] parents;
	static Edge[] edgeList;

	// 단위집합(원소 하나만 있는애) 생성
	public static void makeSet() {
		parents = new int[N];

		// 자신의 부모노드로 자신을 지정
		for (int i = 0; i < N; i++) {
			parents[i] = i;
		}
	}

	// a의 집합 찾기: a의 대표자 찾기
	public static int findSet(int a) {
		if (a == parents[a])
			return a;
		return parents[a] = findSet(parents[a]);// path compression!!
	}

	// a,b 두 집합 합치기
	public static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if (aRoot == bRoot)
			return false; // 대표 같으면 이미 같은집합임

		parents[bRoot] = aRoot;// b의 짱을 a짱 아래에 붙임(=bRoot의 부모가 aRoot이다)
		return true;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		edgeList = new Edge[E];
		
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			edgeList[i] = new Edge(from, to, weight);
		}
		
		Arrays.sort(edgeList); //간선비용 오름차순
		makeSet();
		
		int result = 0, cnt = 0;
		for(Edge edge: edgeList) {
			if(union(edge.from, edge.to)) {
				result += edge.weight;
				if(++cnt == N-1) break;
			}
		}
		System.out.println(result);
	}
}

 

 

프림

아 난 이게 좀 어려웠다. 직관적으로 이해가 안되기 때문이다.

 

키포인트:

1. 얘는 따로 엣지를 안만듦. 정렬시키지도 않는다. 따라서 좀더 빠름.

2. minEdge 배열은 타정점에서 i번째인 나자신에게 오는 간선의 비용중 최소비용을 저장하는 애임. 어디서 오는지는 중요하지 않음. N개의 정점으로 어케든 한번씩 오면 되는거잖아. 누구에게서 오는지는 묻지 않는다.

3. 일단 젤첨엔 minEdge는 다 최댓값으로 채우고, 처음에 시작점(여기선 0)만 시작하는곳이니까 0으로 함.(시작은 걍 거기서 시작하는거니까 비용이 필요없다)

4. min도 최댓값으로 설정하고, 전체 정점을 돌면서 제일 작은 minEdge[i]를 구하고 i를 다음으로 옮길 정점으로 정하고, min(=minEdge[i]로 최신화함)은 i로 이사하는 비용이 됨.

5. 이제 i로 왔어. 근데 i랑 연결된 간선들 중에 기존 minEdge에 저장된 비용보다 더 싼 비용을 발견했을 수 있음. 그럼 minEdge를 최신화시켜줘야 함.

6. 최신화된 minEdge에서 가장 비용이 작은 정점으로 이동!(물론 방문안한곳 중에서)...52~56라인부터 다시시작.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/*
5
0 0 10 8 7 
5 0 5 3 6 
10 5 0 1 3 
8 3 1 0 1 
7 6 3 1 0

output==>12

7
0 32 31 0 0 60 51
32 0 21 0 0 0 0
31 21 0 0 46 0 25
0 0 0 0 34 18 0
0 0 46 34 0 40 51
60 0 0 18 40 0 0
51 0 25 0 51 0 0

output==>175
 */
public class MST2_PrimTest {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		StringTokenizer st = null;
		int[][] adjMatrix = new int[N][N];
		int[] minEdge = new int[N];//타정점에서 자신으로의 간선비용중 최소비용
		boolean[] visited = new boolean[N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for(int j=0; j<N; j++) {
				adjMatrix[i][j] = Integer.parseInt(st.nextToken());
			}
			minEdge[i] = Integer.MAX_VALUE;//충분히 큰값으로 최소값 초기화
		}
		
		int result = 0;//MST 비용
		minEdge[0] = 0; //나 자신은 0
		for(int c=0; c<N; c++) {//N개의 정점을 모두 연결
			//신장트리에 연결되지 않은 정점 중 가장 유리한 비용의 정점을 선택
			int min = Integer.MAX_VALUE;
			int minVertex = 0;//암거나
			System.out.println("=========="+c+"===========");
			System.out.println("minEdge: "+Arrays.toString(minEdge));
			for(int i=0; i<N; i++) {
				if(!visited[i] && min>minEdge[i]) {
					System.out.println("min: "+min+",  minEdge["+i+"]: "+minEdge[i]);
					min = minEdge[i];
					minVertex = i;
				}
			}
			
			//선택된 정점을 신장트리에 포함시킴
			visited[minVertex] = true;
			result += min;
			System.out.println("min: "+min);
			
			//선택된 정점 기준으로 신장트리에 포함되지 않은 다른 정점으로의 간선비용을 따져보고 최소값 갱신
			for(int i=0; i<N; i++) {
				if(!visited[i] && adjMatrix[minVertex][i]!=0 && minEdge[i] > adjMatrix[minVertex][i]) {
					minEdge[i] = adjMatrix[minVertex][i];
				}
			}
			System.out.println("minEdge: "+Arrays.toString(minEdge));
		}
		System.out.println(result);
	}
}

첫번째 예시 출력결과:

==========0===========
minEdge: [0, 2147483647, 2147483647, 2147483647, 2147483647]
min: 2147483647,  minEdge[0]: 0
min: 0
minEdge: [0, 2147483647, 10, 8, 7]
==========1===========
minEdge: [0, 2147483647, 10, 8, 7]
min: 2147483647,  minEdge[2]: 10
min: 10,  minEdge[3]: 8
min: 8,  minEdge[4]: 7
min: 7
minEdge: [0, 6, 3, 1, 7]
==========2===========
minEdge: [0, 6, 3, 1, 7]
min: 2147483647,  minEdge[1]: 6
min: 6,  minEdge[2]: 3
min: 3,  minEdge[3]: 1
min: 1
minEdge: [0, 3, 1, 1, 7]
==========3===========
minEdge: [0, 3, 1, 1, 7]
min: 2147483647,  minEdge[1]: 3
min: 3,  minEdge[2]: 1
min: 1
minEdge: [0, 3, 1, 1, 7]
==========4===========
minEdge: [0, 3, 1, 1, 7]
min: 2147483647,  minEdge[1]: 3
min: 3
minEdge: [0, 3, 1, 1, 7]
12