[백준 1197] - 최소 스패닝 트리(Kruskal's algorithm) C++

문제

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

1197번: 최소 스패닝 트리

접근방법

크루스칼 알고리즘을 사용했다.

 

Edge와 DisjointSet의 클래스를 각각 선언해

사용했다.

 

Kruskal 또는 prim 알고리즘을 구현할 때, 포인트는

Edge 클래스 내에 operator를 선언하는 것이다. 

부등호의 방향이 >임을 잊지말자.

 

DisjointSet 생성자에서

parent와 rank의 크기를 V+1으로 초기화해야하는데,

V로 초기화해서 런타임에러가 떴다. 이런 실수를 주의해야한다.

 

priority_queue를 썼는데, 굳이 쓸 필요는 없을 거 같다.

vector<Edge>로 구현하면 코드가 더 간단해진다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <set>

using namespace std;

#define FOR(i, n) for (int i=0;i<(n);++i)
#define _FOR(i, s, n) for (int i=s;i<(n);++i)
#define FASTER ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define INF 987654321

class Edge {
public:
    int src, dest, weight;
    Edge(int src, int dest, int weight) : src(src), dest(dest),weight(weight) {}
    bool operator<(const Edge& other) const{
        return weight > other.weight;
    }
};

class DisjointSets {
public:
    vector<int> parent, rank;

    DisjointSets(int V) : parent(V+1), rank(V+1, 0) {
        for(int i=0;i<V+1;i++) {
            parent[i] = i;
        }
    }

    int find(int i) {
        if (parent[i] == i) return i;
        return find(parent[i]);
    }

    void unionSet(int x, int y) {
        int xroot = find(x);
        int yroot = find(y);

        if (rank[xroot] < rank[yroot]) {
            parent[xroot] = parent[yroot];
        } else if (rank[xroot] > rank[yroot]) {
            parent[yroot] = parent[xroot];
        } else {
            parent[yroot] = parent[xroot];
            rank[xroot]++;
        }
    }
};

int V, E;
priority_queue<Edge> pq;
vector<vector<Edge>> adj_list;
int answer;



void Kruskal() {
    DisjointSets ds(V);

    while(!pq.empty()) {
        Edge edge = pq.top();
        pq.pop();

        if (ds.find(edge.src) == ds.find(edge.dest)) continue;

        answer += edge.weight;

        ds.unionSet(edge.src, edge.dest);
    }
}

int main () {
    FASTER
    cin >> V >> E;
    answer = 0;
    FOR(i, E) {
        int src, dest, weight;
        cin >> src >> dest >> weight;
        pq.push(Edge(src, dest, weight));
    }
    Kruskal();
    cout << answer << endl;

    return 0;
}

개선할 점

pq.push(Edge(src, dest, weight)) 해도 되고,

pq.push({src, dest, weight})해도 된다.

 

생성자 선언할 때, 

DisjointSets(int V) : parent(V+1), rank(V+1) {};

이렇게도 할 수 있음을 배웠다.