문제 접근
주어진 그래프와 간선정보를 통해 최소 스패닝 트리를 만들고 가중치의 합을 출력해라
문제 조건
- 정점 V의 개수는 (1 <= V <= 100,000)이다
- 간선 E의 개수는 (1 <= E <= 200,000)이다.
- A, B, C는 A와 B를 연결하는 가중치 C를 나타내며 C는 음수일 수도 있으며
- 절대값이 1,000,000을 넘지 않는다.
문제 설계
주어진 정점과 간선의 개수가 많기 때문에 효율적인 알고리즘이 필요
-> 크루스칼 알고리즘과 프림 알고리즘은 주어진 그래프의 최소 스패닝 트리를 만드는 데
최적화된 탐욕기법이 적용된 알고리즘이다.
크루스칼 알고리즘을 통한 구현
크루스칼 알고리즘은 정점과 정점사이 가중치가 제일 작은 간선부터 트리를 만들어나가며 각각의 트리가 같은 집합에 속해있는지 확인하고 합하는 과정을 통해 진행되며, 이 때 각 정점이 속한 그룹을 확인하고 합하는 과정에서 Union-Find 알고리즘이 사용된다.
알고리즘 프로세스
- 모든 정점의 부모노드를 자기 자신으로 초기화한다.
- 입력받은 두 정점에 대한 간선 정보중 작은 가중치를 가진 간선을 우선적으로 가져온다.
- 두 정점을 비교하여 서로 같은 집합에 속해있는지 확인하기 위해 다음 과정을 진행한다.
- 3-1. 두 정점의 부모 노드를 재귀 호출을 통해 반복적으로 탐색하여 각각의 최종 루트 노드를 탐색한다.
- 3-2. 두 정점의 루트 노드가 같으면 둘은 같은 집합에 속해 있으므로 아무것도 진행하지 않는다.
- 3-3. 두 정점의 루트 노드가 다르면 4번을 진행한다.
- 두 루트 노드 중 작은 값이 루트노드가 되도록 합한다.
- 간선의 개수가 정점의 개수(V) - 1 이 될때까지 2 ~ 4번 과정을 반복한다.
Union-Find 알고리즘이란
서로소 집합(Disjoint Set)을 관리하기 위한 알고리즘이다. 이름 그대로 두 가지 핵심 연산인 Union(합치기)과 Find(찾기)로 이루어져 있다.
Find는 3-1 번에서 재귀 호출을 통해 반복적으로 탐색하는 과정에서 만나게 되는 모든 노드들을 전부 최종 루트에 직접 연결해 버려 다음 노드탐색시 최종 노드 탐색시간을 극적으로 압축 시켜버리는 경로 압축을 진행한다.
Union은 합치는 과정에서 무작정 합치지 않고 원칙을 세우는 것이다. 4번의 작은 값이 루트노드가 되도록 합하는 것이 이 Union과정에 해당한다. 이렇게 할 경우 트리가 한쪽으로 길어지는 비효율적인 형태가 되는 것을 막아준다.
구현 코드
package SWEA.D4;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
/**
* 최소 스패닝 트리
*/
public class D4_3124_mst {
static class Node implements Comparable<Node> {
int u;
int v;
int w;
public Node(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(Node o) {
return this.w - o.w;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
// 부모 초기화
int[] parent = new int[V + 1];
// 처음엔 자기자신이 부모노드
for (int i = 1; i <= V; i++) {
parent[i] = i;
}
long result = 0;
// ArrayList를 사용하여 간선정보를 입력 받은 뒤 오름차순 정렬하기
List<Node> arr = new ArrayList<>();
// 간선 정보 입력
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
arr.add(new Node(u, v, w));
}
// 오름차순 정렬
Collections.sort(arr);
// cnt가 V-1개가 될때까지 확인
int cnt = 0;
int idx = 0;
while (cnt < V - 1) {
Node cur = arr.get(idx);
// 두 정점의 부모 노드 탐색
int rootU = find(parent, cur.u);
int rootV = find(parent, cur.v);
// 부모노드가 같지 않아야 합해도 사이클이 되지 않음
if (rootU != rootV) {
// 같지 않으면 합하고 가중치 더하기
result += cur.w;
union(parent, rootU, rootV);
cnt++;
}
idx++;
}
// 출력
System.out.println("#" + tc + " " + result);
}
} // main
// 부모 노드 탐색하면서 바로 부모노드 접근 가능하도록 parent 압축
public static int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
// 부모 노드 return
return parent[x];
}
// 부모 노드가 낮은 쪽이 부모 노드가 되도록 두 트리를 합하기
public static void union(int[] parent, int rootU, int rootV) {
if (rootU > rootV) {
parent[rootV] = rootU;
} else {
parent[rootU] = rootV;
}
}
}
회고
그래프로 넘어오니 주어진 문제 상황에 따라 적용해야하는 알고리즘과 자료구조들이 많아지는거 같다. 그래프 문제를 풀기 위해서는 DFS와 BFS를 아는 것도 중요하지만 문제 조건에 맞는 알고리즘을 사용하기 위해 다양한 유형의 그래프 알고리즘 문제를 접해보는 것이 좋다라는 것을 느꼈다.
