문제
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
입력
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.
그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.
출력
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
풀이
최소 스패닝 트리를 구하는 가장 전형적인 방법은 크루스칼 알고리즘이다. 간선을 가중치 오름차순으로 정렬한 뒤, 사이클이 생기지 않는 간선만 차례대로 채택하면 전체 가중치 합이 최소가 된다.
코드에서는 모든 간선을 edgeList에 저장해 정렬하고, union-find로 두 정점이 이미 같은 집합인지 확인한다. 서로 다른 집합이라면 그 간선을 MST에 포함하고, union()으로 집합을 합치면서 비용을 더한다.
이미 연결된 두 정점을 다시 잇는 간선은 사이클만 만들기 때문에 건너뛰면 된다. 이 과정을 끝까지 반복하면 선택된 간선들의 가중치 합이 최소 스패닝 트리의 정답이 된다.
코드
import java.io.*;
import java.util.*;
public class Main {
static class Edge implements Comparable<Edge> {
int u, v, weight;
public Edge(int u, int v, int weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.weight, o.weight);
}
}
static int[] parent;
static ArrayList<Edge> edgeList;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
edgeList = new ArrayList<>();
parent = new int[V + 1];
for (int i = 1; i <= V; i++)
parent[i] = i;
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
edgeList.add(new Edge(A, B, C));
}
Collections.sort(edgeList);
System.out.println(solve());
}
static int solve() {
int ans = 0;
for (Edge edge : edgeList)
if (union(edge.u, edge.v))
ans += edge.weight;
return ans;
}
static boolean union(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return false;
parent[v] = u;
return true;
}
static int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
}복잡도
- 시간 복잡도: 간선 정렬과 union-find 처리를 수행하므로 이다.
- 공간 복잡도: 간선 목록과 부모 배열을 저장하므로 이다.
마무리
최소 스패닝 트리 문제의 핵심은 결국 가장 가벼운 간선부터 보되, 사이클만 막는 것이다. 그 역할을 union-find가 아주 단순하게 처리해 준다.
