[백준] 1197번 : 최소 스패닝 트리

문제

 

 

---

풀이

 

최소 신장 트리, 최소 스패닝 트리, MST 등등으로 불리는 문제다.

가중치가 있는 간선이 주어진 그래프가 있을 때 가중치의 합이 가장 작은 트리를 만드는 것인데

트리니까 당연히 사이클이 없을 것이고 정점의 수가 V일 때, 최종 간선의 수는 V-1이 될 것이다.

 

이러한 MST를 만드는 대표적인 알고리즘은 크루스칼과 프림이 있는데

크루스칼(kruskal)은 유니온 파인드를 이용해 푸는 알고리즘이고

프림은 다익스트라랑 비슷해보여서 많이들 헷갈리지만 아무튼 둘은 다른 알고리즘이다.

 

ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전

ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

프림 알고리즘 - 위키백과, 우리 모두의 백과사전

난 kruskal로 구현했다.

---

소스코드

 

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

using namespace std;
typedef pair<int, int> pp;

priority_queue<pair<int, pp>, vector<pair<int, pp>>, greater<pair<int, pp>>> pq; //min-heap
vector<int> parent;

int findParent(int x) { //parent[x]가 음수가 될 때까지(root에 다다를 때까지) 재귀 함수 호출
    if (parent[x] < 0)
        return x;
    return parent[x] = findParent(parent[x]);
}

bool unionInput(int x, int y) {
    int x_p = findParent(x); //x의 부모
    int y_p = findParent(y); //y의 부모

    if (x_p == y_p) //이미 같은 집합, 이 간선 쓸 수 없음
        return false;
    if (parent[x_p] < parent[y_p]) { //x_p를 root로 하는 노드가 더 많으면 x_p -> y_p
        parent[x_p] += parent[y_p];
        parent[y_p] = x_p;
    } else { //y_p를 root로 하는 노드가 더 많으면 y_p -> x_p
        parent[y_p] += parent[x_p];
        parent[x_p] = y_p;
    }
    return true;
}

int kruskalMst(int V) {
    int cnt = 0, weight = 0;

    while (cnt != (V - 1)) { //사용한 간선이 V-1개이면 break
        int dist = pq.top().first; //간선의 weight
        int x = pq.top().second.first;
        int y = pq.top().second.second;

        pq.pop();
        if (unionInput(x, y)) { //x, y를 유니온할 수 있다면
            cnt++;
            weight += dist;
        }
    }
    return weight; //그래프의 가중치 합
}

int main() {
    int V, E, A, B, C;

    cin >> V >> E;
    parent.assign(V + 1, -1);
    for (int i = 0; i < E; i++) {
        cin >> A >> B >> C;
        pq.push(make_pair(C, make_pair(A, B)));
    }
    cout << kruskalMst(V);
}

전체 소스코드다.

 

priority_queue<pair<int, pp>, vector<pair<int, pp>>, greater<pair<int, pp>>> pq; //min-heap

가중치가 가장 작은 간선을 꺼내기 위해 min-heap을 사용한다.

 

    parent.assign(V + 1, -1);
    for (int i = 0; i < E; i++) {
        cin >> A >> B >> C;
        pq.push(make_pair(C, make_pair(A, B)));
    }
    cout << kruskalMst(V);

입력을 받으면서 가중치와 연결된 두 정점을 우선순위 큐에 넣고, kruskalMst 함수를 호출한다.

 

int kruskalMst(int V) {
    int cnt = 0, weight = 0;

    while (cnt != (V - 1)) { //사용한 간선이 V-1개이면 break
        int dist = pq.top().first; //간선의 weight
        int x = pq.top().second.first;
        int y = pq.top().second.second;

        pq.pop();
        if (unionInput(x, y)) { //x, y를 유니온할 수 있다면
            cnt++;
            weight += dist;
        }
    }
    return weight; //그래프의 가중치 합
}

트리의 간선 갯수가 V-1이 될 때까지 while문을 돈다.

현재 가중치가 가장 작은 간선에 연결된 두 정점을 꺼내 x, y에 저장하고 이 두 정점을 union할 수 있는지 확인한다.

 

myunji.tistory.com/367

[백준] 1717번 : 집합의 표현

그 부분은 이 문제에서 사용한 유니온 파인드 함수와 거의 동일한 함수를 사용했다.

 

unionInput 함수가 true를 반환했다면 x, y가 유니온 된 것이다. 그럼 간선의 수와 weight를 증가시킨다.

마지막에 최종 weight를 반환하면 된다.