라이브스마트

소개

프로그래밍 시험에서 자주 등장하는 최소 신장 트리(Minimum Spanning Tree, MST) 문제는 주로 그래프 이론의 중요한 개념 중 하나입니다. 최소 신장 트리는 그래프의 모든 정점을 포함하면서 가중치의 합을 최소화하는 트리 구조를 의미합니다.
이 글에서는 Kotlin 언어를 사용하여 최소 신장 트리를 구하는 알고리즘을 자세히 살펴보고, 관련 문제 풀이 예제를 통해 이론을 적용하는 방법을 배워보겠습니다.

기본 개념

그래프

그래프는 정점(vertices)과 간선(edges)으로 구성된 데이터 구조입니다. 정점은 노드, 간선은 노드 사이의 연결을 나타냅니다.
그래프는 방향 그래프와 무방향 그래프로 구분할 수 있으며, 간선에 가중치가 존재하면 가중치 그래프로 불립니다.

최소 신장 트리(MST)

최소 신장 트리는 가중치 그래프에서 모든 정점을 연결하는 서브그래프 중에서 가중치의 합이 최소인 트리입니다.
MST를 찾는 알고리즘으로는 Prim의 알고리즘과 Kruskal의 알고리즘이 널리 사용됩니다.

문제 설명

문제 정의

당신은 무방향 그래프와 그 간선의 가중치가 주어졌습니다. 이 그래프의 모든 정점을 포함하는 최소 신장 트리를 찾아 그 가중치의 합을 출력하는 프로그램을 작성하세요.

입력 형식

• 첫 번째 줄에는 정점의 수 V와 간선의 수 E가 주어집니다. (1 ≤ V ≤ 1000, 1 ≤ E ≤ 10000)
• 다음 E줄에는 간선의 두 정점과 가중치가 주어집니다.

출력 형식

최소 신장 트리의 가중치의 합을 출력합니다.

문제 풀이 과정

Kruskal의 알고리즘을 이용한 접근

Kruskal의 알고리즘은 간선을 가중치 기준으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 최소 신장 트리를 구성하는 방식입니다.
이 알고리즘은 주어진 그래프의 간선을 정렬하고, 유니온-파인드 데이터 구조를 이용하여 사이클 여부를 확인합니다.
이 과정은 다음과 같은 단계로 진행됩니다.

1. 간선 정렬: 모든 간선을 가중치 기준으로 오름차순 정렬합니다.
2. 유니온-파인드 초기화: 각 정점이 독립된 집합으로 초기화합니다.
3. 최소 신장 트리 구축: 정렬된 간선을 순회하며 사이클이 없으면 해당 간선을 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의 알고리즘과 같은 다른 접근법도 존재합니다.
이러한 알고리즘을 활용하면 효율적으로 그래프 문제를 해결할 수 있습니다.
앞으로도 여러 가지 알고리즘을 소개하여 코딩 테스트에서의 성공적인 결과를 거둘 수 있도록 도와드리겠습니다.

1. 최소 신장 트리란?

최소 신장 트리(Minimum Spanning Tree, MST)는 가중치가 부여된 그래프에서 모든 정점을 포함하면서 가중치의 합이 최소가 되도록 하는 부분 그래프를 말합니다. 즉, 트리의 모든 정점이 연결되어 있으며 주어진 간선의 가중치의 합이 가장 작은 트리를 의미합니다. 최소 신장 트리는 네트워크 설계, 도로 건설, 통신망 구축 등 다양한 분야에서 활용됩니다.

2. 알고리즘 문제 제시

다음은 최소 신장 트리를 구하는 문제입니다:

문제 설명

주어진 정점 수 V와 간선 수 E가 있는 그래프가 주어질 때, 최소 신장 트리의 가중치의 합을 구하는 프로그램을 코틀린으로 작성하세요. 간선은 가중치와 함께 주어집니다.

입력 형식

• 첫 번째 줄에 정점 수 V와 간선 수 E가 주어진다.
• 다음 E개의 줄에는 각 간선의 정보 u, v, w (정점 u와 v를 연결하는 간선의 가중치 w)가 주어진다.

출력 형식

최소 신장 트리의 가중치의 합을 출력한다.

3. 문제 해결 방법론

3.1. 알고리즘 선택

최소 신장 트리를 구하는 방법으로는 Prim 알고리즘과 Kruskal 알고리즘이 있습니다. 본 강좌에서는 Prim 알고리즘을 사용하여 문제를 해결하겠습니다. Prim 알고리즘은 다음과 같은 절차로 진행됩니다.

1. 임의의 정점에서 시작하여 연결된 간선 중 가장 가중치가 작은 간선을 선택하여 트리에 포함시킵니다.
2. 트리에 포함된 정점과 연결된 모든 간선 중에서 가중치가 가장 작은 간선을 선택합니다.
3. 이 과정을 모든 정점이 트리에 포함될 때까지 반복합니다.

3.2. 시간 복잡도

Prim 알고리즘의 시간 복잡도는 O(E log V)입니다. 여기서 E는 간선의 수, V는 정점의 수입니다. 반면, Kruskal 알고리즘은 O(E log E)로 비슷하지만 서로 다른 경우에 더 효율적일 수 있습니다.

4. 코틀린 코드 구현

아래는 Prim 알고리즘을 사용한 최소 신장 트리의 가중치 합을 구하는 코틀린 코드입니다:

fun findMinimumSpanningTree(V: Int, edges: List>): Int {
    val graph = Array(V) { mutableListOf>() }
    for (edge in edges) {
        graph[edge.first].add(Pair(edge.second, edge.third))
        graph[edge.second].add(Pair(edge.first, edge.third))
    }

    val visited = BooleanArray(V)
    val minHeap = PriorityQueue>(compareBy { it.second })
    minHeap.add(Pair(0, 0)) // (정점, 가중치)
    var totalWeight = 0

    while (minHeap.isNotEmpty()) {
        val (u, weight) = minHeap.poll()
        if (visited[u]) continue
        visited[u] = true
        totalWeight += weight

        for ((v, w) in graph[u]) {
            if (!visited[v]) {
                minHeap.add(Pair(v, w))
            }
        }
    }

    return totalWeight
}
            

4.1. 메인 함수와 입력 부분

위의 `findMinimumSpanningTree` 함수를 사용할 메인 함수와 입력 처리 부분은 다음과 같습니다:

fun main() {
    val (V, E) = readLine()!!.split(" ").map { it.toInt() }
    val edges = mutableListOf>()

    repeat(E) {
        val edge = readLine()!!.split(" ").map { it.toInt() }
        edges.add(Triple(edge[0], edge[1], edge[2]))
    }

    val result = findMinimumSpanningTree(V, edges)
    println(result)
}
            

5. 문제 풀이 과정에서의 주의 사항

최소 신장 트리를 구하는 과정에서 몇 가지 주의해야 할 사항들이 있습니다:

• 그래프의 정점은 인덱스 0부터 시작하는 경우가 많으므로 입력할 때 주의해야 합니다.
• 모든 정점을 방문해야 하므로, visited 배열의 초기화를 잊지 않도록 합니다.
• 모든 간선의 가중치가 같은 경우에도 알고리즘을 잘 수행할 수 있도록 설계해야 합니다.
• 최종적으로 출력되는 가중치의 합이 올바른지 확인합니다.
• 간선이 중복되지 않도록 처리해야 합니다.

6. 예제 테스트 케이스

다음은 최소 신장 트리 문제를 테스트하기 위한 예제 케이스입니다:

입력 예시

4 5
0 1 1
0 2 3
1 2 1
1 3 4
2 3 1

출력 예시

3

예제 입력은 4개의 정점과 5개의 간선으로 이루어진 그래프입니다. 최소 신장 트리를 구성하는 간선의 가중치의 합은 3이어야 합니다.

7. 결론

이번 강좌에서는 코틀린을 사용하여 최소 신장 트리를 구하는 Prim 알고리즘을 구현해보았습니다. 이 알고리즘은 효율적이며 구현하기도 쉬워 다양한 문제에 적용할 수 있습니다. 알고리즘 문제 풀이 과정에서 그래프의 구조를 이해하고 최적의 방식으로 문제를 해결하는 능력을 키우는 것이 중요합니다. 앞으로도 다양한 알고리즘 문제를 통해 실력을 향상시켜 나가길 바랍니다.