작성일: 2023년 10월 21일
소개
프로그래밍 시험에서 자주 등장하는 최소 신장 트리(Minimum Spanning Tree, MST) 문제는 주로 그래프 이론의 중요한 개념 중 하나입니다. 최소 신장 트리는 그래프의 모든 정점을 포함하면서 가중치의 합을 최소화하는 트리 구조를 의미합니다.
이 글에서는 Kotlin 언어를 사용하여 최소 신장 트리를 구하는 알고리즘을 자세히 살펴보고, 관련 문제 풀이 예제를 통해 이론을 적용하는 방법을 배워보겠습니다.
기본 개념
그래프
그래프는 정점(vertices)과 간선(edges)으로 구성된 데이터 구조입니다. 정점은 노드, 간선은 노드 사이의 연결을 나타냅니다.
그래프는 방향 그래프와 무방향 그래프로 구분할 수 있으며, 간선에 가중치가 존재하면 가중치 그래프로 불립니다.
최소 신장 트리(MST)
최소 신장 트리는 가중치 그래프에서 모든 정점을 연결하는 서브그래프 중에서 가중치의 합이 최소인 트리입니다.
MST를 찾는 알고리즘으로는 Prim의 알고리즘과 Kruskal의 알고리즘이 널리 사용됩니다.
문제 설명
문제 정의
당신은 무방향 그래프와 그 간선의 가중치가 주어졌습니다. 이 그래프의 모든 정점을 포함하는 최소 신장 트리를 찾아 그 가중치의 합을 출력하는 프로그램을 작성하세요.
입력 형식
- 첫 번째 줄에는 정점의 수
V와 간선의 수E가 주어집니다. (1 ≤ V ≤ 1000,1 ≤ E ≤ 10000) - 다음
E줄에는 간선의 두 정점과 가중치가 주어집니다.
출력 형식
최소 신장 트리의 가중치의 합을 출력합니다.
문제 풀이 과정
Kruskal의 알고리즘을 이용한 접근
Kruskal의 알고리즘은 간선을 가중치 기준으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 최소 신장 트리를 구성하는 방식입니다.
이 알고리즘은 주어진 그래프의 간선을 정렬하고, 유니온-파인드 데이터 구조를 이용하여 사이클 여부를 확인합니다.
이 과정은 다음과 같은 단계로 진행됩니다.
- 간선 정렬: 모든 간선을 가중치 기준으로 오름차순 정렬합니다.
- 유니온-파인드 초기화: 각 정점이 독립된 집합으로 초기화합니다.
- 최소 신장 트리 구축: 정렬된 간선을 순회하며 사이클이 없으면 해당 간선을 MST에 추가합니다.
코틀린 구현
코드 예제
class Edge(val u: Int, val v: Int, val weight: Int): Comparable {
override fun compareTo(other: Edge) = this.weight - other.weight
}
class DisjointSet(val size: Int) {
private val parent = IntArray(size) { it }
private val rank = IntArray(size) { 0 }
fun find(x: Int): Int {
if (parent[x] != x) {
parent[x] = find(parent[x])
}
return parent[x]
}
fun union(x: Int, y: Int): Boolean {
val rootX = find(x)
val rootY = find(y)
if (rootX == rootY) return false
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY
} else {
parent[rootY] = rootX
rank[rootX]++
}
return true
}
}
fun kruskal(vertices: Int, edges: List): Int {
val disjointSet = DisjointSet(vertices)
val sortedEdges = edges.sorted()
var totalWeight = 0
for (edge in sortedEdges) {
if (disjointSet.union(edge.u, edge.v)) {
totalWeight += edge.weight
}
}
return totalWeight
}
fun main() {
val reader = System.`in`.bufferedReader()
val (V, E) = reader.readLine().split(" ").map { it.toInt() }
val edges = mutableListOf()
for (i in 0 until E) {
val (u, v, weight) = reader.readLine().split(" ").map { it.toInt() }
edges.add(Edge(u - 1, v - 1, weight))
}
val result = kruskal(V, edges)
println(result)
}
코드 설명
위 코드는 Kruskal의 알고리즘을 기반으로 최소 신장 트리를 찾는 과정입니다.
Edge 클래스는 간선 정보를 저장하며, DisjointSet 클래스는 유니온-파인드 알고리즘에 기반하여 집합의 대표자를 찾고, 두 집합을 합치는 기능을 제공 합니다.
kruskal 함수에서는 입력 받은 정점 수와 간선 목록을 사용하여 모든 간선을 가중치 기준으로 정렬합니다.
그런 다음, 정렬된 간선을 순회하며 사이클이 발생하지 않는 경우에만 해당 간선을 MST에 추가합니다.
마지막으로 MST의 총 가중치를 반환합니다.
테스트 케이스
예제 입력
5 6
1 2 3
1 3 4
2 3 1
2 4 6
3 4 5
4 5 2예제 출력
10설명
주어진 그래프는 5개의 정점과 6개의 간선으로 구성되어 있으며, 이때 최소 신장 트리는 가중치 1, 2, 3, 4의 간선으로 이루어져 총 가중치 10을 갖습니다.
결론
이번 글에서는 코틀린을 사용하여 최소 신장 트리를 찾는 알고리즘을 구현하고, 그 과정에 대한 이해를 높이기 위해 문제를 풀어보았습니다.
최소 신장 트리는 다양한 실제 문제에 적용될 수 있는 중요한 개념이며, Kruskal의 알고리즘 외에도 Prim의 알고리즘과 같은 다른 접근법도 존재합니다.
이러한 알고리즘을 활용하면 효율적으로 그래프 문제를 해결할 수 있습니다.
앞으로도 여러 가지 알고리즘을 소개하여 코딩 테스트에서의 성공적인 결과를 거둘 수 있도록 도와드리겠습니다.