백준 BOJ 1185번 : 유럽여행
문제 난이도 : Platinum IV
알고리즘 분류 : 최소 스패닝 트리 (MST)
트리 형태의 그래프가 주어지고, 한 지점에서 시작하여 어떤 노드와 간선을 지나갈 때의 비용이 모두 주어질 때, 최소 비용으로 모든 노드를 순회할 때 드는 최소 비용을 구하는 문제이다.
경로를 생각해보면, 시작점을 제외하고 어떤 경로든 지나갔다가 다시 돌아와야 하므로, 간선의 시작점 → 간선 → 간선의 끝 점 → 간선 순서로 반드시 지나가게 된다.
따라서 간선의 비용 자체를 (간선의 시작점의 비용 + 간선의 끝 점의 비용 + 간선의 비용 x 2)로 설정해주고, 여기에 시작점으로 설정할 최소 비용인 노드의 비용을 더해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
bool cmp(s x, s y) { return x.c < y.c; }
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> u(N+1);
int Min = INT_MAX;
for(int i=1; i<=N; i++) {
cin >> u[i];
Min = min(Min, u[i]);
}
vector<s> adj(M);
for(int i=0; i<M; i++) {
int a, b, c; cin >> a >> b >> c;
adj[i] = {a, b, c*2 + u[a] + u[b]};
}
sort(adj.begin(), adj.end(), cmp);
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
int ans = 0, cnt = 0;
for(int i=0; i<adj.size(); i++) {
int a = adj[i].a, b = adj[i].b, c = adj[i].c;
if(f(a) == f(b)) continue;
v[f(a)] = f(b);
ans += c;
cnt++;
if(cnt == N-1) break;
}
ans += Min;
cout << ans << "\n";
}
백준 BOJ 2887번 : 행성 터널
문제 난이도 : Platinum V
알고리즘 분류 : 최소 스패닝 트리 (MST)
3차원 공간 상에 N개의 점이 있고, 두 점 사이를 연결하는 비용이 min(|xA-xB|, |yA-yB|, |zA-zB|)이라고 할 때, 모든 점들을 서로 연결하기 위한 최소 비용을 구하는 문제이다.
최소 스패닝 트리 문제임을 바로 알 수 있지만, N이 최대 10만이므로 가능한 모든 비용을 설정하는 것은 불가능하다.
따라서 x, y, z 값들을 각각 정렬해주고, 인접하지 않은 두 값은 어차피 최소가 될 수 없으므로 인접한 N-1쌍들을 adj 벡터에 넣어준다.
즉, adj 벡터에는 (N-1) x 3개의 값들이 들어가는 것이다.
이제 adj 벡터를 정렬해준 뒤 크루스칼 알고리즘을 수행해주면 O(N) 시간에 MST를 찾을 수 있다.
물론 종합적인 시간 복잡도는 정렬을 수행했으므로 O(N log N)이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
bool cmp(s x, s y) { return x.c < y.c; }
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<pair<int, int>> vx(N+1), vy(N+1), vz(N+1);
for(int i=1; i<=N; i++) {
cin >> vx[i].first >> vy[i].first >> vz[i].first;
vx[i].second = vy[i].second = vz[i].second = i;
}
sort(vx.begin()+1, vx.end());
sort(vy.begin()+1, vy.end());
sort(vz.begin()+1, vz.end());
vector<s> adj;
for(int i=2; i<=N; i++) adj.push_back({vx[i-1].second, vx[i].second, vx[i].first - vx[i-1].first});
for(int i=2; i<=N; i++) adj.push_back({vy[i-1].second, vy[i].second, vy[i].first - vy[i-1].first});
for(int i=2; i<=N; i++) adj.push_back({vz[i-1].second, vz[i].second, vz[i].first - vz[i-1].first});
sort(adj.begin(), adj.end(), cmp);
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
int ans = 0, cnt = 0;
for(int i=0; i<adj.size(); i++) {
int a = adj[i].a, b = adj[i].b, c = adj[i].c;
if(f(a) == f(b)) continue;
v[f(a)] = f(b);
ans += c;
cnt++;
if(cnt == N-1) break;
}
cout << ans << "\n";
}
백준 BOJ 6091번 : 핑크 플로이드
문제 난이도 : Gold I
알고리즘 분류 : 최소 스패닝 트리 (MST)
트리에서 플로이드-와셜 알고리즘으로 구한 노드-노드 사이의 최단 거리가 주어졌을 때, 각 노드에 인접해있는 노드들의 목록을 구하는 문제이다. (즉, 트리를 복원하면 된다.)
모든 거리들을 정렬했을 때 최단 거리는 무조건 인접한 노드 사이의 간선이다.
따라서 거리들을 정렬한 뒤 짧은 거리부터 분리 집합을 활용하여 그룹으로 묶어가면서 확인해보면 된다. (두 노드가 같은 그룹이 아닐 경우 서로 인접하다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
bool cmp(s x, s y) { return x.c < y.c; }
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<s> adj;
for(int i=1; i<=N; i++)
for(int j=i+1; j<=N; j++) {
int x; cin >> x;
adj.push_back({i, j, x});
}
sort(adj.begin(), adj.end(), cmp);
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
vector<vector<int>> u(N+1);
for(int i=0; i<adj.size(); i++) {
int a = adj[i].a, b = adj[i].b;
if(f(a) == f(b)) continue;
u[a].push_back(b);
u[b].push_back(a);
v[f(a)] = f(b);
}
for(int i=1; i<=N; i++) {
sort(u[i].begin(), u[i].end());
cout << u[i].size() << " ";
for(int j=0; j<u[i].size(); j++) cout << u[i][j] << " ";
cout << "\n";
}
}
백준 BOJ 1368번 : 물대기
문제 난이도 : Gold II
알고리즘 분류 : 최소 스패닝 트리 (MST)
N개의 논이 있는데 각 논에 서로 다른 비용을 들여 우물을 파도 되고, 또는 N x N 행렬로 a_ij = (i번째 논에서 j번째 논에 물을 끌어오는데 필요한 비용)이 주어질 때 모든 논에 물을 들이기 위해 필요한 최소 비용을 구하는 문제이다.
처음 생각해볼 수 있는 것은 여러 개의 부분 그래프를 만들고 각 부분 그래프에서 우물을 파는 가장 작은 비용을 골라 답에 합산하는 것이다.
그러나 이렇게 구현할 경우 부분 그래프를 어떻게 연결할지가 결정되지 않는다.
이러한 문제의 경우 0번 노드를 하나 만들어서 i번 논에 우물을 파는 비용을 0번 노드와 i번 노드를 연결하는 간선의 비용으로 설정해주고, 0 ~ N번 노드에 대한 최소 스패닝 트리의 비용을 구해주면 된다.
이렇게 구현할 경우 문제에서 요구하는 조건과 완전히 대응되는 그래프가 얻어진다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
bool cmp(s x, s y) { return x.c < y.c; }
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<s> adj;
for(int i=1; i<=N; i++) {
int x; cin >> x;
adj.push_back({0, i, x});
}
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) {
int x; cin >> x;
if(i >= j) continue;
adj.push_back({i, j, x});
}
sort(adj.begin(), adj.end(), cmp);
v.resize(N+1);
for(int i=0; i<=N; i++) v[i] = i;
int ans = 0, cnt = 0;
for(int i=0; i<adj.size(); i++) {
int a = adj[i].a, b = adj[i].b, c = adj[i].c;
if(f(a) == f(b)) continue;
v[f(a)] = f(b);
ans += c;
cnt++;
if(cnt == N) break;
}
cout << ans << "\n";
}
백준 BOJ 23743번 : 방탈출
문제 난이도 : Gold II
알고리즘 분류 : 최소 스패닝 트리 (MST)
위의 문제와 동일한 문제이다.
비용의 개념이 시간의 개념으로 바뀌긴 했지만 풀이도 같으며, 코드 또한 똑같이 구현해주면 된다.
여담으로 이 문제의 기존 난이도가 Gold III이었는데 난이도 기여를 하여 Gold II로 상향 조정되었다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
bool cmp(s x, s y) { return x.c < y.c; }
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<s> adj;
while(M--) {
int a, b, c; cin >> a >> b >> c;
adj.push_back({a, b, c});
}
for(int i=1; i<=N; i++) {
int x; cin >> x;
adj.push_back({0, i, x});
}
sort(adj.begin(), adj.end(), cmp);
v.resize(N+1);
for(int i=0; i<=N; i++) v[i] = i;
int ans = 0, cnt = 0;
for(int i=0; i<adj.size(); i++) {
int a = adj[i].a, b = adj[i].b, c = adj[i].c;
if(f(a) == f(b)) continue;
v[f(a)] = f(b);
ans += c;
cnt++;
if(cnt == N) break;
}
cout << ans << "\n";
}
백준 BOJ 20335번 : Generators
문제 난이도 : Gold I
알고리즘 분류 : 최소 스패닝 트리 (MST)
N개의 섬이 있고 그들 중 M개는 발전소 설치 후보일 때, M개의 줄에 걸쳐 섬의 번호와 설치 비용이 주어지고, N개의 정수 a_i = i번 섬과 i+1번 섬을 연결하는 비용이 주어질 때, 모든 섬들에 전력을 공급하기 위한 최소 비용을 구하는 문제이다.
이 문제 역시 위의 문제와 동일하지만, 이 문제의 경우에는 대놓고 그래프를 떠올릴 수 있는 문제는 아니므로 위의 문제를 이해하고 풀이하는 것이 수월하다.
"발전소 설치 = 0번 노드와의 연결"이라고 생각하고, 0 ~ N번 노드들에 대한 최소 스패닝 트리의 비용을 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
bool cmp(s x, s y) { return x.c < y.c; }
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<s> adj;
while(M--) {
int a, b; cin >> a >> b;
adj.push_back({0, a, b});
}
for(int i=1; i<=N; i++) {
int x; cin >> x;
if(i != N) adj.push_back({i, i+1, x});
else adj.push_back({N, 1, x});
}
sort(adj.begin(), adj.end(), cmp);
v.resize(N+1);
for(int i=0; i<=N; i++) v[i] = i;
int ans = 0, cnt = 0;
for(int i=0; i<adj.size(); i++) {
int a = adj[i].a, b = adj[i].b, c = adj[i].c;
if(f(a) == f(b)) continue;
v[f(a)] = f(b);
ans += c;
cnt++;
if(cnt == N) break;
}
cout << ans << "\n";
}
백준 BOJ 10423번 : 전기가 부족해
문제 난이도 : Gold II
알고리즘 분류 : 최소 스패닝 트리 (MST)
N개의 노드와 M개의 간선이 있는 그래프가 주어지고, K개의 노드는 이미 발전소가 설치되어 있다고 할 때, 적절한 간선들을 선택하여 모든 노드에 전기가 통하도록 하는 최소 비용을 구하는 문제이다.
위의 문제들과 비슷한 방식으로, 0번 노드를 가상으로 만들어 K개의 발전소 노드들과 연결하고 N개의 간선을 갖는 N+1 노드들의 최소 스패닝 트리를 구성하는 최소 비용을 크루스칼 알고리즘으로 구현해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
bool cmp(s x, s y) { return x.c < y.c; }
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
vector<s> adj;
while(K--) {
int x; cin >> x;
adj.push_back({0, x, 0});
}
while(M--) {
int a, b, c; cin >> a >> b >> c;
adj.push_back({a, b, c});
}
sort(adj.begin(), adj.end(), cmp);
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
int ans = 0, cnt = 0;
for(int i=0; i<adj.size(); i++) {
int a = adj[i].a, b = adj[i].b, c = adj[i].c;
if(f(a) == f(b)) continue;
v[f(a)] = f(b);
ans += c;
cnt++;
if(cnt == N) break;
}
cout << ans << "\n";
}
백준 BOJ 5818번 : SPIJUNI
문제 난이도 : Gold II
알고리즘 분류 : 최소 스패닝 트리 (MST)
N x N 행렬로 a_ij = i번째 스파이가 j번째 스파이에게 정보를 전달하는 비용이 주어지고, 마지막 줄에 주어지는 N개의 값에 대해 b_i = i번째 스파이에게 정보를 최초로 전달하는데 필요한 비용이 있다면, 모든 스파이에게 정보를 전달하는데 필요한 최소 비용을 구하는 문제이다.
역시 마찬가지로 최초로 정보를 전달하는 곳을 0번 노드라고 생각하고 간선들을 이은 뒤, N+1개의 노드에 대해 최소 스패닝 트리의 비용을 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
bool cmp(s x, s y) { return x.c < y.c; }
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<s> adj;
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) {
int x; cin >> x;
if(i >= j) continue;
adj.push_back({i, j, x});
}
for(int i=1; i<=N; i++) {
int x; cin >> x;
adj.push_back({0, i, x});
}
sort(adj.begin(), adj.end(), cmp);
v.resize(N+1);
for(int i=0; i<=N; i++) v[i] = i;
int ans = 0, cnt = 0;
for(int i=0; i<adj.size(); i++) {
int a = adj[i].a, b = adj[i].b, c = adj[i].c;
if(f(a) == f(b)) continue;
v[f(a)] = f(b);
ans += c;
cnt++;
if(cnt == N) break;
}
cout << ans << "\n";
}
백준 BOJ 10661번 : Median Tree
문제 난이도 : Gold II
알고리즘 분류 : 최소 스패닝 트리 (MST)
N개의 노드와 M개의 간선을 가지는 그래프가 주어질 때, 이들 중 N-1개의 간선을 선택하여 트리를 만들 때, N-1개의 간선들 중 중앙값이 최소가 되는 트리에서 중앙값을 구하는 문제이다.
크루스칼 알고리즘을 기본적으로 이해하고 있다면 문제의 의도를 파악할 수 있다.
애초에 MST를 구하는 크루스칼 알고리즘은 가장 낮은 비용의 간선부터 검사하면서 트리에 추가하기 때문에, 결국에는 최소 스패닝 트리를 구했을 때 간선들의 중앙값이 최소가 된다.
따라서 최소 스패닝 트리를 구하면서 N/2번째로 추가된 간선을 답으로 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
bool cmp(s x, s y) { return x.c < y.c; }
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
int N, M; cin >> N >> M;
if(N == 0 && M == 0) break;
vector<s> adj(M);
for(int i=0; i<M; i++)
cin >> adj[i].a >> adj[i].b >> adj[i].c;
sort(adj.begin(), adj.end(), cmp);
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
int ans = 0, cnt = 0;
for(int i=0; i<adj.size(); i++) {
int a = adj[i].a, b = adj[i].b, c = adj[i].c;
if(f(a) == f(b)) continue;
v[f(a)] = f(b);
cnt++;
if(cnt == N/2) ans = c;
if(cnt == N-1) break;
}
cout << ans << "\n";
}
}
백준 BOJ 20757번 : Roadside optimization
문제 난이도 : Gold III
알고리즘 분류 : 분리 집합
크기가 N x N인 인접 행렬이 주어졌을 때 해당 형태의 그래프를 만들기 위해서 필요한 최소 간선의 수를 구하는 문제이다.
분리 집합을 이용하여 몇 개의 그룹이 존재하는지를 찾으면, N - (그룹의 개수)가 필요한 최소 간선의 수가 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N; cin >> N;
v.clear();
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) {
int x; cin >> x;
if(i >= j || x == 0) continue;
if(f(i) == f(j)) continue;
v[f(i)] = f(j);
}
vector<int> u;
for(int i=1; i<=N; i++) u.push_back(f(i));
sort(u.begin(), u.end());
u.erase(unique(u.begin(), u.end()), u.end());
int ans = N - u.size();
cout << ans << "\n";
}
}
백준 BOJ 16393번 : Lost Map
문제 난이도 : Gold II
알고리즘 분류 : 최소 스패닝 트리 (MST)
N x N 크기의 행렬이 주어지고 a_ij = i번 마을에서 j번 마을로 가는 도로의 거리라고 할 때, 최소 비용으로 모든 도로를 연결해야 한다면 연결해야 하는 도로들의 목록(양 끝 마을)을 구하는 문제이다.
크루스칼 알고리즘을 활용하여 최소 스패닝 트리를 찾으면 된다.
여담으로 다른 MST 문제들과 비교해 보았을 때 난이도가 높게 책정되어 있다고 생각하여 난이도 기여로 Gold III으로 투표했다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
bool cmp(s x, s y) { return x.c < y.c; }
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<s> adj;
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) {
int x; cin >> x;
if(i >= j) continue;
adj.push_back({i, j, x});
}
sort(adj.begin(), adj.end(), cmp);
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
int ans = 0, cnt = 0;
vector<pair<int, int>> u;
for(int i=0; i<adj.size(); i++) {
int a = adj[i].a, b = adj[i].b, c = adj[i].c;
if(f(a) == f(b)) continue;
v[f(a)] = f(b);
ans += c;
cnt++;
u.push_back({a, b});
if(cnt == N-1) break;
}
for(int i=0; i<u.size(); i++)
cout << u[i].first << " " << u[i].second << "\n";
}
백준 BOJ 20010번 : 악덕 영주 혜유
문제 난이도 : Gold II
알고리즘 분류 : 최소 스패닝 트리 (MST), 트리의 지름
그래프가 주어질 때, 이들 중 일부 간선을 선택하여 연결 비용이 최소가 되도록 할 때 이 때의 비용과 가장 거리가 먼 두 노드 사이의 거리를 구하는 문제이다.
먼저 모든 노드들을 연결 비용이 최소가 되도록 하는 것은 최소 스패닝 트리를 찾으라는 것과 같으므로, 크루스칼 알고리즘으로 풀어주면 된다.
이제 이 그래프에서 가장 거리가 먼 두 점 사이의 거리라는 것은 트리의 지름을 의미하는 것이므로, 선택된 간선들을 추가하여 그래프를 다시 구성해준 뒤, 이 그래프에서 트리의 지름을 찾는 DFS 탐색을 수행해주면 된다.
트리의 지름을 찾는 코드는 백준 BOJ 1167번 : 트리의 지름 문제를 참고하면 도움이 될 것이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
bool cmp(s x, s y) { return x.c < y.c; }
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
vector<vector<pair<int, int>>> ad;
int Max = 0, node = 0;
void g(int cur, int pre, int sum) {
if(sum > Max) {
Max = sum;
node = cur;
}
for(int i=0; i<ad[cur].size(); i++)
if(ad[cur][i].first != pre) g(ad[cur][i].first, cur, sum + ad[cur][i].second);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<s> adj(M);
for(int i=0; i<M; i++)
cin >> adj[i].a >> adj[i].b >> adj[i].c;
sort(adj.begin(), adj.end(), cmp);
v.resize(N);
for(int i=0; i<N; i++) v[i] = i;
int ans = 0, cnt = 0;
vector<s> u;
for(int i=0; i<adj.size(); i++) {
int a = adj[i].a, b = adj[i].b, c = adj[i].c;
if(f(a) == f(b)) continue;
v[f(a)] = f(b);
ans += c;
cnt++;
u.push_back({a, b, c});
if(cnt == N-1) break;
}
ad.resize(N);
for(int i=0; i<u.size(); i++) {
int a = u[i].a, b = u[i].b, c = u[i].c;
ad[a].push_back({b, c});
ad[b].push_back({a, c});
}
g(0, -1, 0);
Max = 0;
g(node, -1, 0);
cout << ans << "\n" << Max << "\n";
}
백준 BOJ 22813번 : Building a Space Station
문제 난이도 : Gold III
알고리즘 분류 : 최소 스패닝 트리 (MST)
3차원 공간 상에 N개의 구가 있고, 접하거나 겹치지 않는 구들에 대해 구의 표면과 표면 사이를 연결하여 모든 구들을 연결할 때, 필요한 길이의 최솟값을 구하는 문제이다.
3차원 공간 상에서 최소 스패닝 트리를 그대로 구현해주면 된다.
구가 만약 접하거나 겹친다면 비용이 0인 간선으로 처리해주고, 그렇지 않은 경우 두 구의 중심 사이의 거리에서 두 구의 반지름의 합을 빼주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { double a, b, c; };
struct ss { double x, y, z, r; };
bool cmp(s x, s y) { return x.c < y.c; }
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(3);
while(true) {
int N; cin >> N;
if(N == 0) break;
vector<ss> u(N+1);
for(int i=1; i<=N; i++)
cin >> u[i].x >> u[i].y >> u[i].z >> u[i].r;
vector<s> adj;
for(int i=1; i<=N; i++)
for(int j=i+1; j<=N; j++) {
double d = sqrt(pow(u[i].x - u[j].x, 2) + pow(u[i].y - u[j].y, 2) + pow(u[i].z - u[j].z, 2));
if(d <= u[i].r + u[j].r) adj.push_back({i, j, 0});
else adj.push_back({i, j, d - (u[i].r + u[j].r)});
}
sort(adj.begin(), adj.end(), cmp);
v.clear();
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
double ans = 0, cnt = 0;
for(int i=0; i<adj.size(); i++) {
double a = adj[i].a, b = adj[i].b, c = adj[i].c;
if(f(a) == f(b)) continue;
v[f(a)] = f(b);
ans += c;
cnt++;
if(cnt == N-1) break;
}
cout << ans << "\n";
}
}
백준 BOJ 23941번 : Cherries Mesh
문제 난이도 : Gold III
알고리즘 분류 : 최소 스패닝 트리 (MST), 분리 집합
N개의 체리가 M개의 검은 설탕으로 연결되어 있고, 나머지 두 체리 쌍들에 대해서는 빨간 설탕으로 연결되어 있으며 검은 설탕은 1의 당도이고 빨간 설탕은 2의 당도라면 일부 설탕을 제거하여 모든 체리를 연결하는 최소 당도를 구하는 문제이다.
우선 최소 스패닝 트리를 만드는 문제이고, 검은 설탕의 당도가 더 작으므로 검은 설탕을 최대한 간선으로 구성해야 한다.
그렇게 때문에 분리 집합을 활용하여 사이클이 생기지 않는 선에서 M개의 검은 설탕 간선으로 노드들을 최대한 연결해주고, 최종적으로 K개의 부분 그래프(트리)가 만들어졌다면 이들은 K-1개의 빨간 설탕으로 연결이 가능하므로 답에 (K-1) * 2를 더해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
bool cmp(s x, s y) { return x.c < y.c; }
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
for(int t=1; t<=T; t++) {
int N, M; cin >> N >> M;
vector<s> adj(M);
for(int i=0; i<M; i++) {
cin >> adj[i].a >> adj[i].b;
adj[i].c = 1;
}
sort(adj.begin(), adj.end(), cmp);
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
int ans = 0, cnt = 0;
for(int i=0; i<adj.size(); i++) {
int a = adj[i].a, b = adj[i].b, c = adj[i].c;
if(f(a) == f(b)) continue;
v[f(a)] = f(b);
ans += c;
cnt++;
if(cnt == N-1) break;
}
vector<int> u;
for(int i=1; i<=N; i++) u.push_back(f(i));
sort(u.begin(), u.end());
u.erase(unique(u.begin(), u.end()), u.end());
ans += (u.size() - 1) * 2;
cout << "Case #" << t << ": " << ans << "\n";
}
}
'알고리즘 > 백준(BOJ) 문제풀이' 카테고리의 다른 글
| 세그먼트 트리 문제 풀이 모음 220924 (1) | 2022.09.24 |
|---|---|
| 백준 BOJ 최대 유량 알고리즘 문제 다시 풀어보기 (Network Flow) (0) | 2022.07.27 |
| [백준 BOJ 알고리즘] 수열에서 a_j - a_i = a_k - a_j인 i < j < k 구하기 (3) | 2022.07.21 |
| 백준 BOJ 14958번 : Rock Paper Scissors 풀이 (FFT, 고속 푸리에 변환) (0) | 2022.06.30 |
| 백준 BOJ 13055번 : K-Inversions 풀이 (FFT, 고속 푸리에 변환) (0) | 2022.06.29 |