문제: 1197번: 최소 스패닝 트리
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int compare(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
return a.second < b.second; // 가중치를 기준으로 오름차순 정렬
}
vector<int> node; // 그래프의 정점
// 정점이 속한 집합의 번호 리턴
// find_set 하면 타고 올라갈때마다 해당 node 의 값을 해당 집합 번호로 바꿔줄 것..
// 다음에 또 접근할 때 아래에서 위까지 타고 올라가는 과정은 반복하지 않기 위함.
int find_set(int u) {
if (u == node[u])
return u;
return node[u] = find_set(node[u]);
}
// 각 정점이 속한 집합 번호를 가져온 후 이 둘의 값이 서로 같지 않으면 합침
// 같을 때는 안 합치는 이유: 이미 같은 집합에 있는 거니까 합칠 필요가 없음;;
void union_(int ur, int vr) {
// 합치기 (ur, vr 이 같은지 여부는 밖에서 판단했기 때문에 여기서는 그냥 합치기만 하면 됨)
node[vr] = ur;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int v, e; // v: 정점의 개수, e: 간선의 개수
cin >> v >> e;
node = vector<int>(v + 1); // 인덱스 접근 편하게 하기 위해서 v+1 만큼..(0번 인덱스 값은 안 쓸 것)
for (int i = 1; i < v + 1; i++)
node[i] = i;
vector < pair<pair<int, int>, int>> edges;
for (int i = 0; i < e; i++) {
int a, b, c; // 간선의 정보
cin >> a >> b >> c; // a번 정점과 b번 정점이 가중치 C인 간선으로 연결되어 있음
pair<int, int> nodes = make_pair(a, b);
pair<pair<int, int>, int> edge = make_pair(nodes, c); // 간선 정보 만들기
edges.push_back(edge);
}
sort(edges.begin(), edges.end(), compare); // 가중치를 기준으로 오름차순 정렬할 것..
long long sum = 0; // 최소 스패닝 트리의 가중치
int idx = 0;
int edgeCnt = 0;
// 선택된 간선의 개수가 노드 개수 - 1 의 값이랑 같아질때까지 반복..
// 그리고 edges 에서 더이상 쓸 요소가 없으면 그때도 종료..
while ((edgeCnt < v - 1) && (idx < edges.size())) {
// 가중치가 가장 작은 요소 가져옴(현재 기준으로..)
pair<pair<int, int>, int> tmp = edges[idx++];
// 각 정점이 속한 집합 번호 가져오기
int ur = find_set(tmp.first.first);
int vr = find_set(tmp.first.second);
if (ur != vr) {
union_(ur, vr);
sum += tmp.second; // 가중치 더해주기 ^0^
}
}
cout << sum << "\n";
return 0;
}
MST 도 별거 없었다. 그냥 기존에 배웠던 Disjoints Set 을 이용해서 사이클 여부를 판단한 후, 현재 넣으려고 하는 간선에 의해 사이클이 발생한다고 판단되면 포기하고 다음 간선으로 넘어가면 되는 것이었다.
지금 구하려고 하는게 MST 의 가중치 합이니까 진짜로 가중치가 작은 애들의 간선을 모아서 합하면 되는 것이었다.
그러면 MST 를 구현하는 방법에 대해 조금 더 자세하게 설명해보자면 다음과 같다. 우선 MST 를 구현하는 방법은 Kruskal's Algorithm 과 Prim's Algorithm 으로 총 2개가 존재하는데 이 중 나는 Kruskal's Algorithm 을 이용했다.
Kruskal's Algorithm 의 핵심은 Cycle 을 만들지 않는 최소 간선을 MST 에 반복하여 추가하는 것이다. 즉 이를 위해서 입력받은 간선들을 가중치 값을 기준으로 해서 오름차순 정렬을 해야한다.
간선들을 다 정렬을 하고 난 다음에는 본격적으로 사용할 간선들을 선택해야 한다. 총 골라야 하는 간선의 개수는 정점-1 개와 같다. 즉, while 문을 현재까지 선택된 간선의 개수가 정점-1 개보다 작을때까지 돌도록 했다.
간선들을 이미 가중치를 기준으로 오름차순 정렬을 했기 때문에 이를 저장해놓은 배열에서 순서대로 간선을 가져오면 된다. 만약 간선을 가져왔는데, 두 노드가 이미 연결되어 있다면 이 간선은 포기하고 다음으로 넘어가도록 하면 된다. 반복문을 돌면서 선택되는 간선의 가중치를 최종 합에다가 더해주면 문제가 풀린다.
근데 나는 간선들을 벡터말고 최소힙에 저장하는 식으로 하고 싶었는데 만약 요소가 pair 형태일 때, 두번째 요소를 기준으로 최소힙을 만드는 방법을 모르겠어서 일단은 포기했다. 그래서 찾아본 정보는 다음과 같다.
우선 우선순위 큐를 pair 와 함께 사용할 때 디폴트는 첫번째 요소를 기준으로 정렬을 하다가 값이 같으면 그제서야 두번째 요소를 기준으로 정렬을 한다. 근데 이를 반대로 하고 싶다면 어떻게 해야 하는가..
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
일단 이게 첫번째 요소를 기준으로 최소힙을 만드는 디폴트 형태이다. 여기서 greater 가 pair 의 첫 번째 요소를 기준으로 최소힙을 만들도록 구현되어 있다. 즉, pair 의 두 번째 요소를 기준으로 최소힙을 만들려고 하면 사용자 정의 비교 함수 만든다음에 greater 를 대신해서 넣어주면 된다.
bool compare(pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
}
greater 를 대신해서 만든 compare 함수이다. 근데 이를 처음에 보고 의아했던 점은 return a.second > b.second 이 부분이었다. 사실 sort 함수를 이용할 때, 얘는 디폴트가 오름차순 정렬이라 내림차순 정렬하고 싶을 때 a.second>b.second 이런 식으로 해줬었는데, 지금은 최소힙을 만들려고 하는데 a.second > b.second 를 리턴하는 것이었다.
이유를 찾아보니 다음과 같았다.
sort 함수sort의 기본 정렬 순서는 오름차순입니다.따라서 내림차순으로 정렬하려면 a > b (혹은 a.second > b.second) 조건을 사용해야 합니다.
priority_queue (기본 최대 힙)priority_queue의 기본 정렬 순서는 내림차순입니다. (즉, 가장 큰 값이 맨 위에 위치)최소 힙을 만들려면 greater 또는 커스텀 비교 함수에서 반대로 작성해야 하므로 a > b가 아닌 a < b (혹은 a.second > b.second)를 사용합니다.
이렇게 알아두고 다음에 사용하면 될 것 같다 ^0^
참고자료:
[C++] 힙(Heap)과 Priority q.. : 네이버블로그