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

안녕하세요! 이번 블로그 포스트에서는 C++을 이용한 코딩 테스트에서 자주 출제되는 문제 중 하나인 최소 신장 트리(Minimum Spanning Tree)에 대해 다뤄보겠습니다. 우리는 Prim 알고리즘과 Kruskal 알고리즘을 사용할 것이며, 구체적인 문제를 풀어보며 이론을 정리할 것입니다.

문제 설명

다음과 같은 그래프가 주어질 때, 최소 신장 트리를 구하시오. 최종적으로 트리의 가중치의 합을 출력한다.

여기서 입력의 구조는 다음과 같습니다:

첫 번째 줄: 정점의 수 V와 간선의 수 E
그 다음 E개의 줄: 각 간선의 정보 (정점1, 정점2, 가중치)

문제 해결 방법

위의 문제를 해결하기 위해 Prim 알고리즘과 Kruskal 알고리즘을 사용할 수 있습니다. 여기서는 Prim 알고리즘을 사용하여 문제를 풀어보겠습니다. Prim 알고리즘은 임의의 정점에서 시작해, 가장 작은 가중치의 간선을 선택하여 점차 그래프를 확장하는 방식입니다.

1. Prim 알고리즘 개요

Prim 알고리즘은 다음의 단계로 이루어집니다:

시작 정점을 선택하고, 이에 연결된 간선 중에서 최소 가중치의 간선을 선택합니다.
선택한 간선에 연결된 정점을 포함시킵니다.
위의 과정을 반복하여 모든 정점을 포함할 때까지 진행합니다.

2. C++로 Prim 알고리즘 구현하기

이제 Prim 알고리즘을 C++로 구현해보겠습니다. 이 구현을 통해 실제 문제를 해결하는 과정을 살펴보겠습니다.


#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAX_V = 100; // 최대 정점 수
const int INF = 1e9; // 무한대 표시

vector> graph[MAX_V]; // 인접 리스트
int key[MAX_V]; // 최소 가중치 배열
bool inMST[MAX_V]; // MST 포함 여부

int prim(int start, int V) {
    priority_queue, vector>, greater>> pq;
    fill(key, key + V, INF);
    fill(inMST, inMST + V, false);

    key[start] = 0; // 시작 정점의 키 값은 0
    pq.push({0, start}); // (가중치, 정점)

    int totalWeight = 0; // 최소 신장 트리의 총 가중치

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (inMST[u]) continue; // 이미 MST에 포함된 경우

        totalWeight += key[u]; // 총 가중치에 현재 정점의 키 값을 추가
        inMST[u] = true; // MST에 추가

        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;

            // 현재 간선이 MST에 포함되지 않고, 가중치가 더 작은 경우
            if (!inMST[v] && weight < key[v]) {
                key[v] = weight; // 최소 가중치 업데이트
                pq.push({key[v], v}); // 큐에 추가
            }
        }
    }

    return totalWeight;
}

int main() {
    int V, E;
    cin >> V >> E;

    for (int i = 0; i < E; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        // 0-indexed로 저장
        graph[u - 1].push_back({v - 1, weight});
        graph[v - 1].push_back({u - 1, weight});
    }

    cout << prim(0, V) << endl; // 시작 정점 0
    return 0;
}

3. 코드 설명

위 코드의 설명은 다음과 같습니다:

그래프는 인접 리스트를 사용하여 표현합니다. 각 정점은 연결된 정점과 그 가중치를 가지는 리스트로 되어 있습니다.
우선순위 큐를 사용하여 현재 정점에서 연결된 간선 중 최소 가중치의 간선을 효율적으로 선택합니다.
MST에 포함된 정점은 inMST 배열로 관리합니다.
최종적으로 모든 정점을 포함한 MST의 총 가중치를 반환합니다.

4. 실행 예시

입력 데이터를 실행하면 다음과 같은 결과가 나옵니다:

출력 결과:

Kruskal 알고리즘을 통한 최소 신장 트리 구하기

Prim 알고리즘에 이어, Kruskal 알고리즘을 사용하여 동일한 문제를 해결하는 방법을 살펴보겠습니다. Kruskal 알고리즘은 간선을 기준으로 동작하며, 모든 간선을 가중치 기준으로 정렬한 후 작은 것부터 추가하는 방식입니다.

1. Kruskal 알고리즘 개요

Kruskal 알고리즘은 다음의 단계로 이루어집니다:

간선을 가중치 기준으로 정렬합니다.
가장 작은 간선을 선택하여 사이클이 생기지 않는 경우 MST에 추가합니다.
모든 간선을 처리할 때까지 반복합니다.

2. C++로 Kruskal 알고리즘 구현하기

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


#include 
#include 
#include 
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 u) {
    if (parent[u] != u) {
        parent[u] = find(parent, parent[u]); // 경로 압축
    }
    return parent[u];
}

void unionSet(int parent[], int rank[], int u, int v) {
    int root_u = find(parent, u);
    int root_v = find(parent, v);
    
    if (root_u != root_v) {
        if (rank[root_u] > rank[root_v]) {
            parent[root_v] = root_u;
        } else if (rank[root_u] < rank[root_v]) {
            parent[root_u] = root_v;
        } else {
            parent[root_v] = root_u;
            rank[root_u]++;
        }
    }
}

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

    int totalWeight = 0; // MST의 총 가중치
    for (Edge edge : edges) {
        int u = edge.u, v = edge.v;
        
        // 사이클이 발생하지 않는 경우 MST에 추가
        if (find(parent, u) != find(parent, v)) {
            unionSet(parent, rank, u, v);
            totalWeight += edge.weight; // 가중치 추가
        }
    }
    
    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;
        edges[i].u--; // 0-indexed
        edges[i].v--; // 0-indexed
    }

    cout << kruskal(V, edges) << endl; // MST의 총 가중치 출력
    return 0;
}

3. 코드 설명

위 코드의 설명은 다음과 같습니다:

간선을 저장하는 구조체 Edge를 정의합니다.
간선을 가중치 기준으로 정렬합니다.
유니온-파인드(Union-Find) 자료구조를 이용해 사이클을 체크하고, 사이클이 발생하지 않으면 간선을 MST에 추가합니다.

4. 실행 예시

입력 데이터를 실행하면 다음과 같은 결과가 나옵니다:

출력 결과:

결론

이번 시간에는 최소 신장 트리 문제를 Prim 알고리즘과 Kruskal 알고리즘을 통해 해결하는 방법에 대해 배우았습니다. 각 알고리즘의 특징과 실제 구현 방식을 이해하는 것이 중요하며, 다양한 문제를 해결하기 위해 이러한 알고리즘을 숙지해야 합니다.

최소 신장 트리 문제는 그래프 이론의 기본 개념 중 하나이며, 알고리즘 문제에서도 자주 등장합니다. 위의 구현을 활용하여 다양한 그래프 문제를 효율적으로 해결할 수 있도록 연습하시기 바랍니다.

뷰어 여러분께서도 이 강좌가 도움이 되었기를 바라며, 추가적인 질문이 있으면 댓글로 남겨주세요. 다음 포스트에는 또 다른 알고리즘 문제를 다룰 예정입니다. 감사합니다!

문제 설명

문제 해결 방법

1. Prim 알고리즘 개요

2. C++로 Prim 알고리즘 구현하기

3. 코드 설명

4. 실행 예시

Kruskal 알고리즘을 통한 최소 신장 트리 구하기

1. Kruskal 알고리즘 개요

2. C++로 Kruskal 알고리즘 구현하기

3. 코드 설명

4. 실행 예시

결론

관련