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

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

---

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

문제 설명:

가중치가 있는 무방향 그래프에서 모든 정점을 연결하는 부분 그래프 중 가중치의 합이 최소가 되는 그래프를 찾는 문제입니다. 이러한 그래프를 "최소 스패닝 트리(MST)"라고 합니다.

---

문제 해결 코드

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

// 간선을 저장하는 벡터
vector<pair<int, pair<int, int>>> edges;
int parent[10001]; // 부모 노드 저장 배열

// 부모 노드 찾기 (경로 압축)
int getParent(int n) {
    if (parent[n] == n) return n;
    return parent[n] = getParent(parent[n]);
}

// 두 노드 연결
void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

// 두 노드가 같은 부모를 가지는지 확인
bool findParent(int a, int b) {
    return getParent(a) == getParent(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;
        edges.push_back({c, {a, b}}); // 가중치를 기준으로 정렬
    }

    // 간선 정렬 (가중치 기준 오름차순)
    sort(edges.begin(), edges.end());

    int mstWeight = 0; // 최소 스패닝 트리의 총 가중치

    // 간선을 하나씩 선택
    for (int i = 0; i < edges.size(); i++) {
        int weight = edges[i].first;
        int u = edges[i].second.first;
        int v = edges[i].second.second;

        // 두 노드가 같은 집합에 속하지 않으면 연결
        if (!findParent(u, v)) {
            unionParent(u, v);
            mstWeight += weight;
        }
    }

    // 최소 스패닝 트리의 총 가중치 출력
    cout << mstWeight << '\n';

    return 0;
}

예제 입력:

3 3
1 2 1
2 3 2
1 3 3

예제 출력:

3

---

코드 설명

• 핵심 알고리즘: 크루스칼 알고리즘을 사용하여 간선의 가중치를 기준으로 정렬한 후, 사이클이 발생하지 않도록 간선을 선택하여 최소 스패닝 트리를 구성합니다.
• 구현 세부사항:
  • getParent: 경로 압축을 통해 노드의 부모를 찾습니다.
  • unionParent: 두 노드를 연결합니다.
  • findParent: 두 노드가 같은 집합에 속하는지 확인합니다.
  • 간선을 가중치 기준으로 정렬하고, 사이클이 발생하지 않는 간선만 선택하여 MST를 구성합니다.
• 시간 복잡도:
  • 간선 정렬: O(E log E), E는 간선의 개수
  • 유니온 파인드: O(α(V)), V는 정점의 개수 (α는 아커만 함수의 역함수로 거의 상수)
  • 전체 복잡도: O(E log E)

---

결과

입력된 그래프에서 최소 스패닝 트리의 총 가중치를 정확히 계산합니다. 크루스칼 알고리즘과 유니온 파인드의 개념을 이해하고 구현하기에 적합한 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!