1197. 최소 스패닝 트리

1197. 최소 스패닝 트리

 

 

최소 신장 트리(MST)를 구하는 기본적인 문제이다.

• MST는 머리, 손, 발, 몸통이 따로 있다고 할 때, 말 그대로 키(신장)가 가장 작도록 모든 노드를 연결하는 트리다.
• N개의 노드가 있을 때, MST의 간선 개수는 항상 N - 1이 된다.
• 유니온-파인드를 필수적으로 활용해 크루스칼 알고리즘을 이용한다.

 

1. 가중치의 오름차순으로 정렬된 간선 리스트를 만든다.
2. 연결된 간선 개수가 N - 1이 될때까지 반복한다.
3. 간선 리스트에서 간선을 하나씩 꺼내, 대표 노드가 같지 않을 때(싸이클이 생기지 않을 때)만 union으로 대표 노드끼리 연결한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <numeric>

using namespace std;

int findRep(vector<int>& rep, int i)
{
    if (rep[i] == i)
        return i;
    
    return rep[i] = findRep(rep, rep[i]);
}

bool unionAB(vector<int>& rep, int a, int b)
{
    int repA = findRep(rep, a);
    int repB = findRep(rep, b);

    if (repA == repB)
        return false;

    rep[repA] = rep[repB] = min(repA, repB);

    return true;
}

struct Edge
{
    int s;
    int e;
    int w;

    friend bool operator < (const Edge& A, const Edge& B) { return A.w > B.w; }
};

int main(int argc, char* argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int V, E;
    cin >> V >> E;

    priority_queue<Edge> edges;

    while (E--)
    {
        int s, e, w;
        cin >> s >> e >> w;

        edges.push({s, e, w});
    }

    int nConnected = 0, answer = 0;
    vector<int> rep(V + 1);

    iota(rep.begin(), rep.end(), 0);

    while (nConnected < V - 1)
    {
        Edge edge = edges.top(); edges.pop();

        if (unionAB(rep, edge.s, edge.e))
        {
            answer += edge.w;
            ++nConnected;
        }
    }

    cout << answer;

    return 0;
}

 

우선순위 큐보다는 벡터에 담은 후 정렬하는 것이 더 빠르다.

 

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

using namespace std;

int findRep(vector<int>& rep, int i)
{
    if (rep[i] == i)
        return i;
    
    return rep[i] = findRep(rep, rep[i]);
}

bool unionAB(vector<int>& rep, int a, int b)
{
    int repA = findRep(rep, a);
    int repB = findRep(rep, b);

    if (repA == repB)
        return false;

    rep[repA] = rep[repB] = min(repA, repB);

    return true;
}

struct Edge
{
    int s;
    int e;
    int w;

    friend bool operator < (const Edge& A, const Edge& B) { return A.w < B.w; }
};

int main(int argc, char* argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int V, E;
    cin >> V >> E;

    vector<Edge> edges;

    while (E--)
    {
        int s, e, w;
        cin >> s >> e >> w;

        edges.push_back({s, e, w});
    }

    sort(edges.begin(), edges.end());

    int nConnected = 0, answer = 0;
    vector<int> rep(V + 1);

    iota(rep.begin(), rep.end(), 0);

    for (Edge& edge : edges)
    {
        if (unionAB(rep, edge.s, edge.e))
        {
            answer += edge.w;

            if (V - 1 <= ++nConnected)
                break;
        }
    }

    cout << answer;

    return 0;
}