반응형
방금 프로그래머스에서 풀어본 방식인 크루스칼 알고리즘으로 풀어보았다.
여기서 좀 헷갈렸고, 놓쳤던 부분은 parent를 설정할 때 정점이 1부터 시작한다는 것으로 생각해야하고,
그래서 V + 1 사이즈로 초기화해야한다.
// MST(Minimum Spanning Tree)
// 최소 신장 트리는 두 종류 알고리즘으로 풀 수 있다.
// 크루스칼 알고리즘 VS 프림 알고리즘
// 크루스칼 알고리즘은 간선을 선택하며 찾는 알고리즘
// 프림 알고리즘은 정점을 선택하며 찾는 알고리즘이다.
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
long long V, E;
long long getRoot(vector<long long>& parent, long long x) {
if (parent[x] == x) return x;
return parent[x] = getRoot(parent, parent[x]);
}
void unionParent(vector<long long>& parent, long long a, long long b) {
a = getRoot(parent, a);
b = getRoot(parent, b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
bool find(vector<long long>& parent, long long a, long long b) {
a = getRoot(parent, a);
b = getRoot(parent, b);
if (a == b) return true;
else return false;
}
bool compare(vector<long long> a, vector<long long> b) {
return a[2] < b[2];
}
int main() {
scanf("%lld %lld", &V, &E);
vector<vector<long long>> costs;
// Costs Initialize
for (long long e = 0; e < E; ++e) {
vector<long long> temp;
long long A, B, C;
scanf("%lld %lld %lld", &A, &B, &C);
temp.push_back(A);
temp.push_back(B);
temp.push_back(C);
costs.push_back(temp);
}
sort(costs.begin(), costs.end(), compare);
// Parent Initialize
vector<long long> parent(V + 1);
for (long long i = 1; i <= V; ++i) {
parent[i] = i;
}
int answer = 0;
for (long long i = 0; i < costs.size(); ++i) {
if (!find(parent, costs[i][0], costs[i][1])) {
unionParent(parent, costs[i][0], costs[i][1]);
answer += costs[i][2];
}
}
printf("%d", answer);
return 0;
}
반응형
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
백준 4386 별자리 만들기 (0) | 2021.05.06 |
---|---|
백준 9372 상근이의 여행 (0) | 2021.05.05 |
백준 1708 볼록 껍질 (0) | 2021.04.29 |
백준 11758 CCW (0) | 2021.04.28 |
백준 14500 테트로미노 (0) | 2021.04.26 |