⚡ 그래프 최소 비용 (MST)
📌 서로소 집합(Disjoint-sets)
🔷 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다.
- 교집합이 없다.
🔷 대표자(representative)
- 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다.
🔷 서로소 집합 연산
1) Make-Set(x): 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산
2) Find-Set(x): x를 포함하는 집합을 찾는 연산 (대표자를 리턴)
3) Union(x, y): x와 y를 포함하는 두 집합을 통합하는 연산. x와 y는 대표자이며 y가 x를 가리키게 된다.
💡 Find-Set, Union 연산을 합쳐 Union-Find 알고리즘이라고 부른다.
🔷 서로소 집합 표현 방법
1) 연결 리스트
- 같은 집합의 원소들은 하나의 연결리스트로 관리한다.
- 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.
- 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다.
2) 트리
- 하나의 집합을 하나의 트리로 표현한다.
- 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다.
🔷 연산의 효율을 높이는 방법
1) Rank를 이용한 Union
-
각 노드는 자신을 루트로 하는 subtree의 높이를 rank라는 이름으로 저장한다.(
Make-Set연산 시) -
두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다.
💡 랭크가 같을 때는 둘 중 하나를 붙일 집합으로 임의 선정한다.
static void makeset(int i) {
p[i] = i;
rank[i] = 0;
}2) Path Compression
Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾼다.
static int findset(int x) {
if(x != p[x])
p[x] = findset(p[x]);
return p[x];
}static void union(int x, int y) {
int findX = findset(x);
int findY = findset(y);
if(rank[findX] > rank[findY])
p[findY] = findX;
else {
p[findX] = findY;
if(rank[findX] == rank[findY])
rank[findY]++;
}
}📌 최소 신장 트리(MST)
🔷 신장 트리
- 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리
🔷 최소 신장 트리
- 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리
- 특징
1) 무방향 가중치 그래프
2) 그래프의 가중치의 합이 최소여야 한다.
3) N개의 정점을 가지는 그래프에 대해 반드시 (N-1)개의 간선을 사용해야 한다.
4) 사이클을 포함해서는 안된다. - 도로망, 통신망, 유통망 등등 여러 분야에서 비용을 최소로 해야 이익을 볼 수 있어 사용한다.
- 대표적으로
Kruskal과Prim알고리즘이 있다.
⭐ 크루스칼 알고리즘(KRUSKAL Algorithm)
🔷 간선을 하나씩 선택해서 MST를 찾는 알고리즘
1) 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬
2) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴
- 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
💡 Find-Set을 통해 대표자가 같음이 확인되면 사이클이라는 뜻이므로 거를 수 있다.
3) n-1 개의 간선이 선택될 때 까지 2)를 반복
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class DailyAPS {
static int [] p; //대표자 저장 배열
public static void main(String[] args) {
Scanner sc = new Scanner(input);
int V = sc.nextInt(); //정점의 개수 0부터 시작
int E = sc.nextInt(); //간선의 수
//간선 배열을 만들어서 저장(2차원 배열)
//[0]: 시작정점, [1]: 끝정점, [2]: 가중치
int[][] edges = new int[E][3];
for(int i =0; i < E; i++) {
edges[i][0] = sc.nextInt();
edges[i][1] = sc.nextInt();
edges[i][2] = sc.nextInt();
}
//크루스칼 1단계: 간선을 가중치 오름차순으로 정렬
Arrays.sort(edges, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[2] - o2[2];
}
});
//크루스칼 2단계: V-1개의 간선 뽑기 (사이클이 발생해서는 안된다)
p = new int[V];
//2-1 Make-Set
for(int i = 0; i < V; i++) {
makeset(i);
}
//2-2 검사하면서 뽑기
int ans = 0; //최소 비용을 저장할 변수
int pick = 0; //뽑은 간선의 수를 저장할 변수
//for문 (if 조건을 통해 break)
for(int i = 0; i < E; i++) {
//i번째 간선을 이용하여 두개의 정점을 가지고 처리
int x = edges[i][0];
int y = edges[i][1];
if(findset(x) != findset(y)) {
//사이클이 형성이 안됐다는 조건 하
union(x, y);
ans += edges[i][2];
pick++;
}
if(pick == V-1) break;
}
System.out.println(ans);
}
static String input = "7 11\r\n" +
"0 1 32\r\n" +
"0 2 31\r\n" +
"0 5 60\r\n" +
"0 6 51\r\n" +
"1 2 21\r\n" +
"2 4 46\r\n" +
"2 6 25\r\n" +
"3 4 34\r\n" +
"3 5 18\r\n" +
"4 5 40\r\n" +
"4 6 51\r\n" +
"\r\n";
static void makeset(int i) {
p[i] = i;
//rank 생략
}
static int findset(int x) {
// 패스 컴프레션
if(x != p[x])
p[x] = findset(p[x]);
return p[x];
}
static void union(int x, int y) {
p[findset(y)] = findset(x); // x의 대표를 y의 대표로 넣는다. rank는 고려되지 않는다.
}
}
Hodie mihi, Cras tibi