백준 1197번 [최소 스패닝 트리](C++) -yes6686- 티스토리

백준 문제 풀이: 1197 [최소 스패닝 트리]

---

문제 링크: https://www.acmicpc.net/problem/1197

문제 설명:

가중치가 있는 무방향 그래프가 주어질 때, 최소 스패닝 트리(MST)를 구성하는 간선들의 가중치 합을 계산하는 문제입니다. MST는 다음 조건을 만족해야 합니다:

• 그래프의 모든 정점이 연결되어 있어야 합니다.
• 간선의 가중치 합이 최소가 되어야 합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

// 우선순위 큐와 Union-Find를 이용해 최소 스패닝 트리를 구성
priority_queue<pair<int, pair<int, int>>, 
    vector<pair<int, pair<int, int>>>, 
    greater<>> pq;

int parent[10001]; // 부모를 저장하는 배열

// Union-Find 알고리즘: Find 연산
int findParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = findParent(parent[x]);
}

// Union-Find 알고리즘: Union 연산
void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

// 두 노드가 같은 부모를 갖는지 확인
bool isSameParent(int a, int b) {
    return findParent(a) == findParent(b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int V, E; // 정점의 개수와 간선의 개수
    cin >> V >> E;

    // 부모 배열 초기화
    for (int i = 1; i <= V; i++) {
        parent[i] = i;
    }

    // 간선 정보 입력
    for (int i = 0; i < E; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        pq.push({C, {A, B}});
    }

    int totalCost = 0; // MST의 총 비용

    // 크루스칼 알고리즘으로 최소 스패닝 트리 구성
    while (!pq.empty()) {
        int cost = pq.top().first;
        int a = pq.top().second.first;
        int b = pq.top().second.second;
        pq.pop();

        // 두 정점이 같은 집합에 속하지 않으면 간선을 추가
        if (!isSameParent(a, b)) {
            unionParent(a, b);
            totalCost += cost;
        }
    }

    // 결과 출력
    cout << totalCost << '\n';

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 크루스칼 알고리즘을 사용하여 최소 스패닝 트리를 구성합니다. 간선의 가중치를 기준으로 정렬하고, Union-Find를 이용해 간선 추가 여부를 결정합니다.
• 구현 세부사항:
  • pq: 간선을 가중치 기준으로 정렬하기 위한 우선순위 큐
  • findParent: 경로 압축을 사용해 부모 노드를 찾습니다.
  • unionParent: 두 정점을 같은 집합으로 합칩니다.
  • 크루스칼 알고리즘은 최소 가중치의 간선을 순차적으로 추가하며 트리를 확장합니다.
• 시간 복잡도 분석:
  • 간선 정렬: O(E log E), 여기서 E는 간선의 수
  • Union-Find 연산: O(E log V), 여기서 V는 정점의 수
  전체 시간 복잡도는 O(E log E + E log V)입니다.

---

결과

최소 스패닝 트리를 구성하는 간선들의 가중치 합이 정확히 출력됩니다. 크루스칼 알고리즘의 효율성과 Union-Find 알고리즘의 최적화된 연산을 활용한 풀이입니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!