C++ 코딩테스트 강좌, 최소 신장 트리 구하기

본 강좌에서는 최소 신장 트리(Minimum Spanning Tree, MST)에 대해 배워보겠습니다. 최소 신장 트리는 가중치가 있는 그래프에서 모든 정점을 포함하면서도 가중치의 총합이 최소가 되도록 하는 트리입니다. 이러한 문제는 여러 분야에서 응용 가능하며, 특히 네트워크 설계, 도로 건설, 통신망 구축 등에서 중요한 역할을 합니다.

문제 설명

다음과 같은 가중치가 있는 무방향 그래프가 주어졌을 때, 최소 신장 트리를 구하시오.

입력:
첫 줄에 정점의 수 V와 간선의 수 E가 주어진다. (1 ≤ V ≤ 1000, 1 ≤ E ≤ 10000)
다음 E줄에는 각각의 간선 정보 u, v, w가 주어진다. 이는 정점 u와 정점 v를 연결하는 간선의 가중치가 w라는 의미이다.

출력:
최소 신장 트리의 가중치 총합을 출력하시오.

예제 입력

3 3
1 2 1
2 3 2
1 3 3

예제 출력

3

해결 방법

이 문제를 해결하기 위해 Prim 알고리즘 또는 Kruskal 알고리즘을 사용할 수 있습니다. 여기서는 Kruskal 알고리즘을 사용하여 풀이해보겠습니다.

Kruskal 알고리즘 설명

Kruskal 알고리즘은 간선 기반의 알고리즘으로, 다음과 같은 단계로 진행됩니다:

  1. 모든 간선을 가중치의 오름차순으로 정렬한다.
  2. 정점 집합을 초기화한다. (Union-Find 자료구조를 사용)
  3. 간선을 하나씩 선택하여 두 정점이 서로 연결되어 있지 않으면 이 간선을 선택한다. 이런 과정을 반복하여 모든 정점을 연결하는 최소 신장 트리를 만든다.

코드 구현

이제 C++로 Kruskal 알고리즘을 구현해보겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int u, v, weight;
};

bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

int find(int parent[], int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}

void unionSet(int parent[], int rank[], int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);

    if (rootX != rootY) {
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

int kruskal(int V, vector& edges) {
    sort(edges.begin(), edges.end(), compare);
    int parent[V + 1];
    int rank[V + 1];
    for (int i = 0; i <= V; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    int totalWeight = 0;
    for (Edge edge : edges) {
        if (find(parent, edge.u) != find(parent, edge.v)) {
            totalWeight += edge.weight;
            unionSet(parent, rank, edge.u, edge.v);
        }
    }
    return totalWeight;
}

int main() {
    int V, E;
    cin >> V >> E;
    vector edges(E);
    for (int i = 0; i < E; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
    }
    cout << kruskal(V, edges) << endl;
    return 0;
}

코드 설명

먼저, Edge 구조체를 정의하고 비교 함수로 가중치를 기준으로 정렬합니다.

find 함수는 경로 압축 기법을 사용하여 효율적으로 부모 노드를 찾습니다. unionSet 함수는 두 정점의 집합을 합치는 역할을 하며, 랭크를 사용하여 트리가 너무 커지지 않도록 합니다.

메인 함수에서는 입력을 받고 Kruskal 알고리즘을 통해 최소 신장 트리의 가중치 총합을 구하여 출력합니다.

복잡도 분석

Kruskal 알고리즘의 시간 복잡도는 O(E log E)입니다. 이는 간선 정렬에 소요되는 시간입니다. Union-Find의 연산을 최적화할 경우 매우 효율적인 알고리즘으로 작동합니다.

결론

최소 신장 트리는 많은 실제 문제에서 사용되므로 이를 체계적으로 이해하는 것이 중요합니다. 본 예제를 통해 Kruskal 알고리즘을 적용하여 MST를 찾는 방법을 학습하였으며, 다양한 변형 문제에도 적용할 수 있는 기반 이론을 습득하게 되었습니다. 추가적으로 Prim 알고리즘도 실습해보시길 권장합니다.

다음 강좌에서는 최소 신장 트리에 대한 다른 알고리즘이나 다양한 문제 풀기를 다룰 예정이니 많은 기대 바랍니다.