BOJ: 최소 스패닝 트리(1197) [C++]

https://www.acmicpc.net/problem/1197

 

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

 

 

 

최소신장트리(MST)를 구하는 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있다.

크루스칼로 풀이를 해보자

크루스칼 알고리즘은 유니온파인드를 이용해 MST를 구한다. 현재 선택할 수 있는 간선 중 가중치가 가장 작은 간선부터 선택해나가는데, 사이클이 발생하지 않아야 하므로 유니온파인드의 연산을 사용하는 것.

간선의 수에 영향을 받으며, 간선 수가 E일 때 O(ElogE)의 시간복잡도를 가진다.

최소신장트리의 간선개수는 정점 수 - 1이므로 그만큼 간선을 다 골랐다면 종료한다.

 

유니온 파인드 연산

typedef tuple<int, int, int>tp;
vector<int> parent;

int findParent(int x){
    if(parent[x]<0) return x;
    return parent[x] = findParent(parent[x]);
}

bool unionNodes(int x, int y){
    int px = findParent(x);
    int py = findParent(y);
    if(px==py) return false;
    if(parent[px]<parent[py]) swap(px,py);
    parent[py] += parent[px];
    parent[px] = py;
    return true;
}

 

크루스칼 알고리즘

int kruskal(int v, vector<tp> edge){
    int sum=0, cnt=0;
    for(auto[w, n1, n2]: edge){
        if(!unionNodes(n1, n2)){ //사이클이 생길 경우
            continue;
        }
        sum += w;
        cnt++;
        if(cnt==v-1){ //간선 v-1개 모두 선택함
            return sum;
        }
    }
    return 0; //최소신장트리 만들지 못한 경우
}

 

전체 코드

가중치가 작은 것부터 선택해야 하므로 크루스칼 알고리즘을 사용하기 위해서는 간선을 저장한 배열이 가중치 순서대로 정렬되어야 한다.

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

using namespace std;

typedef tuple<int, int, int>tp;
vector<int> parent;

int findParent(int x){
    if(parent[x]<0) return x;
    return parent[x] = findParent(parent[x]);
}

bool unionNodes(int x, int y){
    int px = findParent(x);
    int py = findParent(y);
    if(px==py) return false;
    if(parent[px]<parent[py]) swap(px,py);
    parent[py] += parent[px];
    parent[px] = py;
    return true;
}

int kruskal(int v, vector<tp> edge){
    int sum=0, cnt=0;
    for(auto[w, n1, n2]: edge){
        if(!unionNodes(n1, n2)){ //사이클이 생길 경우
            continue;
        }
        sum += w;
        cnt++;
        if(cnt==v-1){ //간선 v-1개 모두 선택함
            return sum;
        }
    }
    return 0; //최소신장트리 만들지 못한 경우
}

int main()
{
    int v,e,a,b,c;
    cin >> v >> e;
    vector<tp> edge;
    parent.assign(v+1, -1);
    
    while(e--){
        cin >> a >> b >> c;
        edge.push_back({c,a,b});
    }
    sort(edge.begin(), edge.end()); //가중치 순으로 정렬
    cout << kruskal(v, edge);

    return 0;
}