#include <bits/stdc++.h>
using namespace std;
vector<int> p(10001, -1);
tuple<int, int, int> edges[100001];
int v, e, ans, cnt;
int find_root(int x)
{
if (p[x] < 0) return x; // 루트는 자기 자신이 부모노드이다
return p[x] = find_root(p[x]);
}
int union_root(int a, int b)
{
a = find_root(a);
b = find_root(b);
if (a == b) return false;
if (p[a] == p[b]) p[a]--; // union by rank. 트리의 깊이를 조정해줌
if (p[a] < p[b]) p[b] = a;
else p[a] = b;
return true;
}
int main(void)
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> v >> e;
for (int i = 0; i < e; ++i)
{
int a, b, c;
cin >> a >> b >> c;
edges[i] = {c, a, b};
}
sort(edges, edges + e);
for (int i = 0; i < e; ++i)
{
int a, b, c;
tie(c, a, b) = edges[i];
if (!union_root(a, b)) continue;
ans += c;
cnt++;
if (cnt >= v - 1) break;
}
cout << ans;
return 0;
}
크루스칼 알고리즘 버전
이코테에서 습득했던 구현과 조금 달라서 매치시키는데 이해가 좀 많이걸렸음
이코테 및 다른사람들의 코드를 보면 find의 조건문이 p[x] < 0이 아닌 p[x] != x (혹은 p[x] == x)로 되어있는데 무슨차이가 있냐면 전자는 각 정점의 루트노드를 선언과 동시에 -1로 초기화 시켜서 0 미만인 경우 해당 정점이 루트라는걸 알아내는 것이고 후자는 중간에 각 노드의 루트노드를 자기 자신으로 초기화 시키는 부분이 추가되어있다.
구현상의 차이가 있을뿐 결과는 똑같이 나온다.
추가로 union에서의 if(p[a] == p[b]) p[a]--; 이부분은 트리가 균등하지 않게 깊어지는 경우 성능 하락이 발생하는것을 방지해주는 코드이다. 없어도 시간복잡도는 로그스케일로 나오긴 한다
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int v, e, ans;
vector<pair<int, int>> adj[10005]; // 비용, 정점의 번호
bool chk[10005];
int cnt = 0;
priority_queue< tuple<int, int, int>,
vector<tuple<int, int, int>>,
greater<tuple<int, int, int>>> pq;
int main(void)
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> v >> e;
for (int i = 0; i < e; ++i)
{
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({ c, b });
adj[b].push_back({ c, a });
}
chk[1] = true;
for (auto& nxt : adj[1])
pq.push({ nxt.X, 1, nxt.Y });
while (cnt < v - 1)
{
int a, b, c;
tie(c, a, b) = pq.top(); pq.pop();
if (chk[b]) continue;
chk[b] = true;
ans += c;
cnt++;
for (auto& nxt : adj[b]) {
if (!chk[nxt.Y])
pq.push({ nxt.X, b, nxt.Y });
}
}
cout << ans;
return 0;
}
프림 알고리즘 버전
