8월 5일부터 8월 8일까지 약 53문제 정도를 풀었는데, 문제가 너무 많아서 밀린 풀이를 적을 엄두가 안 난다.
그래서 이 때 풀이한 문제들은 일단 보류해두기로 했다.
그리고 코드포스 Div.2 라운드를 하나 참가했는데, 지금 실력만 유지한다면 조만간 퍼플에 갈 수 있을 것 같다.
시간이 남는다면 해당 라운드의 A~E까지 풀이 정리를 한 번 해보려고 한다.
아무튼 여기서는 오늘(8월 9일) 풀이한 백준 풀이를 다룬다.
백준 BOJ 11085번 : 군사 이동
문제 난이도 : Gold III
알고리즘 분류 : 분리 집합
두 도시(노드) 사이의 경로 중 가장 너비가 작은 간선의 너비가 최대가 되도록 할 때 가장 작은 너비를 구하는 문제이다.
태그가 분리 집합으로 되어 있어서 처음에는 어떻게 유니온 파인드로 풀어야 할지 고민했는데, 정렬을 사용해야 한다.
각 간선의 너비에 대해 내림차순 정렬을 해준 뒤 너비가 큰 간선부터 연결하면서 sour 노드와 dest 노드가 연결 관계가 되는 최초 시점에서 마지막으로 추가한 간선의 너비가 답이 된다.
참고로 이 문제에서 간선의 정보가 주어질 때 start와 end라고 나오는데 그와 관계 없이 양방향 간선으로 연결해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
struct s { int a, b, c; };
bool cmp(s x, s y) {
return x.c > y.c;
}
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;
int sour, dest; cin >> sour >> dest;
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
vector<s> u(M);
for(int i=0; i<M; i++) cin >> u[i].a >> u[i].b >> u[i].c;
sort(u.begin(), u.end(), cmp);
for(int i=0; i<M; i++) {
int a = u[i].a, b = u[i].b, c = u[i].c;
if(f(a) != f(b)) {
v[f(a)] = f(b);
}
if(f(sour) == f(dest)) {
cout << c << "\n";
break;
}
}
}
백준 BOJ 4156번 : Driving Range
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합
N개의 도시와 M개의 "거리가 주어지는" 도로가 있을 때, 모든 도시 사이를 이동할 수 있으며 이 때 이용하는 도로 중 가장 긴 도로의 길이가 최소가 되게 했을 때 그 때의 가장 긴 도로의 길이를 구하는 문제이다.
일단 접근법은 위의 문제와 동일하게, 도로가 얼마나 많은지는 관계 없으므로 길이가 짧은 도로들부터 추가하면서 모든 도시가 연결되는 시점에서의 도로 길이를 답으로 얻으면 된다.
그러나 이 문제에서는 모든 도시가 연결되었는지를 O(N)보다 짧은 시간에 판단해야 시간 초과를 피할 수 있다.
따라서 부분 그래프의 크기를 저장하는 벡터 또한 따로 선언해주어 이를 더해주는 방식으로 답을 구해야 한다.
개인적으로 필요한 개념이 하나 더 있어서 위의 문제보다 어려웠다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
struct s { int a, b, c; };
bool cmp(s x, s y) {
return x.c < y.c;
}
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;
v.clear();
v.resize(N);
for(int i=0; i<N; i++) v[i] = i;
vector<s> u(M);
for(int i=0; i<M; i++)
cin >> u[i].a >> u[i].b >> u[i].c;
sort(u.begin(), u.end(), cmp);
vector<int> w(N, 1);
bool flag = false;
for(int i=0; i<M; i++) {
int a = u[i].a, b = u[i].b, c = u[i].c;
if(f(a) != f(b)) {
w[f(b)] += w[f(a)];
v[f(a)] = f(b);
}
if(w[f(b)] == N) {
cout << c << "\n";
flag = true;
break;
}
}
if(!flag) cout << "IMPOSSIBLE\n";
}
}
백준 BOJ 16724번 : 피리 부는 사나이
문제 난이도 : Gold III
알고리즘 분류 : 분리 집합
각 칸에서 특정 방향으로 이동하는 맵이 주어질 때, 몇 개의 칸들을 선택하여 해당 칸들로 수렴하게 만들기 위한 최소 선택 칸 수를 구하는 문제이다.
이 문제도 분리 집합으로 풀이가 가능한데, 각 칸에 해당하는 노드 번호를 부여하고 이동해서 도달하게 되는 노드들을 연결하여 몇 개의 부분 그래프가 존재하는지 구해주면 된다.
#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 N, M; cin >> N >> M;
v.resize(N*M);
for(int i=0; i<N*M; i++) v[i] = i;
for(int i=0; i<N*M; i++) {
char c; cin >> c;
int a = i, b;
if(c == 'D') b = i + M;
else if(c == 'U') b = i - M;
else if(c == 'R') b = i + 1;
else if(c == 'L') b = i - 1;
if(f(a) != f(b)) v[f(a)] = f(b);
}
vector<int> u;
for(int i=0; i<N*M; i++) u.push_back(f(i));
sort(u.begin(), u.end());
u.erase(unique(u.begin(), u.end()), u.end());
cout << u.size() << "\n";
}
백준 BOJ 17250번 : 은하철도
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합
각 은하의 행성의 개수가 주어지고, 은하 사이에 도로를 놓을 때 새 도로를 이용할 수 있는 행성의 수를 매 도로마다 구하는 문제이다.
분리 집합을 이용하여 새로 연결한 간선에 대해 도달 가능한 은하들의 행성의 수의 합들을 매번 구해주면 된다.
#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 N, M; cin >> N >> M;
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
vector<int> u(N+1);
for(int i=1; i<=N; i++) cin >> u[i];
while(M--) {
int a, b; cin >> a >> b;
if(f(a) != f(b)) {
u[f(b)] += u[f(a)];
v[f(a)] = f(b);
}
cout << u[f(b)] << "\n";
}
}
백준 BOJ 20955번 : 민서의 응급 수술
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합
그래프가 주어졌을 때 이 그래프를 트리로 만들기 위해서 간선을 끊거나 추가하는 연산을 거칠 때, 필요한 최소 연산 횟수를 구하는 문제이다.
간선을 끊어야 하는 경우는 사이클이 존재할 때이고, 사이클이 하나 존재할 때마다 하나씩 끊어야 한다.
사이클의 존재 유무는 두 노드 사이에 간선을 추가하기 전 이미 두 노드가 연결 관계에 있다면 사이클이 만들어지게 되므로 분리 집합을 이용하여 확인할 수 있다.
간선을 추가해야 하는 경우는 두 노드가 다른 부분 그래프일 때이고, N개의 부분 그래프가 존재한다면 이들을 연결하기 위해 N-1개의 간선이 필요하다.
이것은 간선을 모두 추가한 뒤 분리 집합이 몇 개 존재하는지를 카운트하여 확인해줄 수 있다.
#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 N, M; cin >> N >> M;
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
int ans = 0;
while(M--) {
int a, b; cin >> a >> b;
if(f(a) != f(b)) v[f(a)] = f(b);
else ans++;
}
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;
cout << ans << "\n";
}
백준 BOJ 23324번 : 어려운 모든 정점 쌍 최단 거리
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합
단순 연결 그래프가 주어지고 간선들 중 하나의 가중치만 1일 때, 모든 노드 쌍에 대해 두 노드 간 이동 거리들의 합을 구하는 문제이다.
간선들 중 하나의 가중치만 1이므로, 이 간선을 잇는 두 노드를 기준으로 생각해보면 된다.
먼저 두 노드 사이를 다른 경로로 도달할 수 있다면, 모든 이동 거리들의 합은 0이 된다.
왜냐하면 가중치 1짜리 간선을 사용하지 않아도 모든 노드 사이에 이동이 가능하다는 의미이기 때문이다.
이것은 분리 집합으로 탐색이 가능하다.
만약 두 노드 사이에 다른 경로가 존재하지 않는다면, 가중치가 1인 간선을 기준으로 노드들을 양쪽의 두 그룹으로 나눌 수 있다.
이제 이 두 그룹의 노드들을 세어 곱해주면, 모든 경우의 수가 되므로 이것이 답이 된다.
이 역시 분리 집합으로 아래와 같이 구현이 가능하다.
#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 N, M, K; cin >> N >> M >> K;
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
int x, y;
for(int i=1; i<=M; i++) {
int a, b; cin >> a >> b;
if(i == K) {
x = a;
y = b;
continue;
}
if(f(a) != f(b)) v[f(a)] = f(b);
}
if(f(x) == f(y)) {
cout << 0 << "\n";
return 0;
}
int cntx = 0, cnty = 0;
for(int i=1; i<=N; i++) {
if(v[f(i)] == v[f(x)]) cntx++;
else if(v[f(i)] == v[f(y)]) cnty++;
}
int ans = cntx * cnty;
cout << ans << "\n";
}
백준 BOJ 4143번 : Bridges and Tunnels
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합, 해시를 사용한 집합과 맵
N개의 줄에 걸쳐 도시의 이름 두 개가 쌍으로 주어지고 이 도시 둘을 다리로 잇는다고 할 때, 각 다리가 생길 때마다 해당 다리를 이용할 수 있는 도시의 수를 구하는 문제이다.
분리 집합으로 다리들을 연결하면서 두 도시를 연결하는 다리를 기준으로, 두 도시에서 도달할 수 있는 도시의 수를 구하면 된다.
이 때, 도시가 새로 주어진 도시인지 기존에 있던 도시인지를 파악하기 위해 map을 사용하여 체크해주어야 한다.
번호 대신 map 값을 사용하므로 함수, 배열이 이중 삼중으로 쓰여 조금 헷갈릴 수 있으니 표현에 주의해야 한다.
#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(1e5 + 1);
for(int i=1; i<=1e5; i++) v[i] = i;
vector<int> u(1e5 + 1, 1);
int cnt = 1;
map<string, int> m;
while(N--) {
string a, b; cin >> a >> b;
if(m[a] == 0) m[a] = cnt++;
if(m[b] == 0) m[b] = cnt++;
if(f(m[a]) != f(m[b])) {
u[f(m[b])] += u[f(m[a])];
v[f(m[a])] = f(m[b]);
}
cout << u[f(m[b])] << "\n";
}
}
}
백준 BOJ 25187번 : 고인물이 싫어요
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합
그래프의 연결이 주어지고 각 노드가 청정수인지 고인물인지가 주어질 때, 연결된 그래프 내에서 청정수가 더 많으면 청정수를 얻을 수 있다고 할 때 주어지는 노드들에서 청정수를 얻을 수 있는지를 구하는 문제이다.
먼저 같은 부분 그래프 내에서는 청정수와 고인물의 개수가 공유되므로, 분리 집합을 이용하여 연결된 그래프 사이에 청정수와 고인물의 개수를 합쳐주어야 한다.
따라서 벡터 u에는 청정수의 개수, w에는 고인물의 개수를 저장한 뒤 간선이 연결될 때 같은 그래프로 합쳐진다면 청정수와 고인물의 개수를 합쳐주는 방식을 이용하면 된다.
이 때 이들의 합은 최상위 노드에 저장해준다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v, u, w;
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;
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
u.resize(N+1);
w.resize(N+1);
for(int i=1; i<=N; i++) {
int x; cin >> x;
if(x == 1) u[i] = 1;
else w[i] = 1;
}
while(M--) {
int a, b; cin >> a >> b;
if(f(a) != f(b)) {
u[f(b)] += u[f(a)];
w[f(b)] += w[f(a)];
v[f(a)] = f(b);
}
}
while(K--) {
int x; cin >> x;
if(u[f(x)] > w[f(x)]) cout << 1 << "\n";
else cout << 0 << "\n";
}
}
백준 BOJ 14926번 : Not Equal
문제 난이도 : Silver I
알고리즘 분류 : 그래프 탐색, 오일러 경로
N개의 변수에 대해 1대1로 대응이 되는 모든 관계를 이어서 나타내는 사전순으로 가장 빠른 문자열을 구하는 문제이다.
그러니까 예를 들어 N = 5일 때 (a1, a2), (a2, a3), ...와 같이 표현해서 a1 a2 a3 a1 a4 a2 a5 a3 a4 a5 a1으로 답을 구해주면 된다.
설명이 조금 부족한데 문제 원문을 참고하면 도움이 될 것이다.
이 문제를 같은 조건의 다른 상황으로 대응시켜 설명하면, N개의 노드를 가지는 완전 그래프에 대해 1번 노드에서 출발하여 모든 경로를 사전순으로 가장 빠른 노드부터 방문하는 식으로 탐색하면 되는 문제이다. (= 오일러 경로)
따라서 다음과 같이 그래프를 탐색하는 코드를 구현해주면 된다.
완전 그래프에서 1번 노드와 N번 노드 사이의 연결을 끊고 탐색을 진행한 뒤 마지막으로 N번 노드에서 1번 노드로 되돌아오도록 해주면 구현이 조금 더 간편하다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<vector<bool>> v(N+1, vector<bool>(N+1));
v[1][N] = v[N][1] = true;
int cur = 0;
for(int i=0; i<N*(N-1)/2; i++) {
for(int j=1; j<=N; j++) {
if(j == cur || v[cur][j]) continue;
v[cur][j] = v[j][cur] = true;
cur = j;
break;
}
cout << "a" << cur << " ";
}
cout << "a" << 1 << "\n";
}
백준 BOJ 9025번 : Widest Path
문제 난이도 : Gold III
알고리즘 분류 : 분리 집합
위의 백준 BOJ 11085번 : 군사 이동 문제와 동일한 문제이다.
테스트케이스 여러 개만 돌아갈 수 있도록 해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
struct s { int a, b, c; };
bool cmp(s x, s y) {
return x.c > y.c;
}
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, M; cin >> N >> M;
int sour, dest; cin >> sour >> dest;
v.clear();
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
vector<s> u(M);
for(int i=0; i<M; i++) cin >> u[i].a >> u[i].b >> u[i].c;
sort(u.begin(), u.end(), cmp);
for(int i=0; i<M; i++) {
int a = u[i].a, b = u[i].b, c = u[i].c;
if(f(a) != f(b)) {
v[f(a)] = f(b);
}
if(f(sour) == f(dest)) {
cout << c << "\n";
break;
}
}
}
}
백준 BOJ 13244번 : Tree
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합
주어진 그래프가 트리인지 아닌지를 판별하는 문제이다.
주어진 그래프가 연결 그래프가 아니거나 (= 한 덩어리가 아니거나), 이미 같은 덩어리인 두 노드 사이에 간선이 추가될 경우 (= 사이클이 존재할 경우) 트리가 아니다.
따라서 이 두 가지를 검사하여 모두 아니면 tree이고, 그 외의 경우에는 graph를 출력해주면 된다.
이는 역시 분리 집합으로 구현이 가능하다.
#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, M; cin >> N >> M;
v.clear();
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
bool check = true;
while(M--) {
int a, b; cin >> a >> b;
if(f(a) == f(b)) check = false;
else v[f(a)] = f(b);
}
for(int i=1; i<=N; i++)
if(f(i) != f(1)) check = false;
if(check) cout << "tree\n";
else cout << "graph\n";
}
}
백준 BOJ 4803번 : 트리
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합
주어진 그래프에 대해 트리가 몇 개 존재하는지 구하는 문제이다.
트리가 여러 개 존재할 수 있다는 말은 모든 부분 그래프에 대하여 탐색하면 된다는 뜻이다.
문제가 되는 부분은 사이클이 생기면 해당 부분 그래프는 더 이상 트리가 아니라는 것이다.
따라서 분리 집합을 통해 간선마다 각 그래프를 연결해주면서, 사이클이 생기면 (= 이미 연결된 두 노드 사이에 간선이 생기면) w 벡터의 해당 노드의 최상위 노드에 해당하는 번호에 true로 체크를 해두어 마지막에 count 할 때 제외하도록 한다.
반례가 생길 수 있는 부분은 사이클이 생긴 이후 간선이 또 생겨서 최상위 노드가 바뀌는 경우이다.
따라서 연결되지 않은 두 노드 사이의 간선을 새로 연결할 때도 w 벡터 값을 체크하여 갱신해주도록 하자.
자세한 구현은 아래의 코드를 참고하면 도움이 될 것이다.
#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);
for(int t=1; ; t++) {
int N, M; cin >> N >> M;
if(N == 0 && M == 0) break;
v.clear();
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
vector<bool> w(N+1);
while(M--) {
int a, b; cin >> a >> b;
if(f(a) == f(b)) w[f(a)] = true;
else {
if(w[f(a)] || w[f(b)]) w[f(a)] = w[f(b)] = true;
v[f(a)] = f(b);
}
}
vector<int> u;
for(int i=1; i<=N; i++) {
if(w[f(i)]) continue;
u.push_back(f(i));
}
sort(u.begin(), u.end());
u.erase(unique(u.begin(), u.end()), u.end());
cout << "Case " << t << ": ";
if(u.size() == 0) cout << "No trees.\n";
else if(u.size() == 1) cout << "There is one tree.\n";
else if(u.size() >= 2) cout << "A forest of " << u.size() << " trees.\n";
}
}
백준 BOJ 1939번 : 중량제한
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합
위의 백준 BOJ 11085번 : 군사 이동, 백준 BOJ 9025번 : Widest Path 문제와 동일한 문제이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
struct s { int a, b, c; };
bool cmp(s x, s y) {
return x.c > y.c;
}
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;
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
vector<s> u(M);
for(int i=0; i<M; i++)
cin >> u[i].a >> u[i].b >> u[i].c;
sort(u.begin(), u.end(), cmp);
int sour, dest; cin >> sour >> dest;
for(int i=0; i<M; i++) {
int a = u[i].a, b = u[i].b, c = u[i].c;
if(f(a) != f(b)) v[f(a)] = f(b);
if(f(sour) == f(dest)) {
cout << c << "\n";
break;
}
}
}
백준 BOJ 13905번 : 세부
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합
이 문제 역시 위의 문제와 동일하다.
다만, 이 문제의 경우에는 출발점에서 도착점까지 도달하지 못하는 단절된 그래프가 테스트케이스에 존재한다. (즉, 연결 그래프라는 보장이 없다.)
따라서 모든 간선을 추가했음에도 sour와 dest가 같은 부분 그래프에 속하지 않는다면 1개도 목적지까지 옮길 수 없으므로 0을 출력해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
struct s { int a, b, c; };
bool cmp(s x, s y) {
return x.c > y.c;
}
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;
int sour, dest; cin >> sour >> dest;
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
vector<s> u(M);
for(int i=0; i<M; i++)
cin >> u[i].a >> u[i].b >> u[i].c;
sort(u.begin(), u.end(), cmp);
for(int i=0; i<M; i++) {
int a = u[i].a, b = u[i].b, c = u[i].c;
if(f(a) != f(b)) v[f(a)] = f(b);
if(f(sour) == f(dest)) {
cout << c << "\n";
return 0;
}
}
cout << 0 << "\n";
}
백준 BOJ 7547번 : Heavy Transportation
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합
역시 위의 문제와 동일하다.
다만 이 문제는 출발점이 1번 노드, 도착점이 N번 노드로 고정되어 있고, 출발점에서 도착점까지의 경로가 존재한다는 보장이 되어있다.
다음과 같이 똑같이 풀이해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
struct s { int a, b, c; };
bool cmp(s x, s y) {
return x.c > y.c;
}
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;
v.clear();
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
vector<s> u(M);
for(int i=0; i<M; i++)
cin >> u[i].a >> u[i].b >> u[i].c;
sort(u.begin(), u.end(), cmp);
for(int i=0; i<M; i++) {
int a = u[i].a, b = u[i].b, c = u[i].c;
if(f(a) != f(b)) v[f(a)] = f(b);
if(f(1) == f(N)) {
cout << "Scenario #" << t << ":\n";
cout << c << "\n\n";
break;
}
}
}
}
백준 BOJ 9001번 : Rectangle Coloring
문제 난이도 : Gold V
알고리즘 분류 : 분리 집합
2차원 평면에 N개의 직사각형들이 주어지고, 한 점이라도 겹치는 두 직사각형은 같은 색으로 칠한다면 최대 몇 개의 색이 필요한지를 구하는 문제이다.
O(N^2) 시간에 모든 직사각형 쌍들을 비교해보면서 겹치는지 확인해보고, 겹친다면 같은 그룹으로 묶으면 된다. (by 분리 집합)
두 직사각형이 겹치는 부분을 어떻게 하면 간편하게 체크할 수 있는지 고민해보았는데, 다음과 같이 4개의 조건식을 두어서 (오른쪽 변이 다른 직사각형 왼쪽 변보다 왼쪽에 있거나 등등) 하나라도 만족한다면 안 겹친다고 할 수 있다.
자세한 구현은 코드의 check = false 부분을 참고하자.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
struct s { int x1, y1, x2, y2; };
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;
vector<s> u(N+1);
for(int i=1; i<=N; i++)
cin >> u[i].x1 >> u[i].y1 >> u[i].x2 >> u[i].y2;
for(int i=1; i<=N; i++)
for(int j=i+1; j<=N; j++) {
bool check = true;
if(u[i].x1 > u[j].x2) check = false;
if(u[i].x2 < u[j].x1) check = false;
if(u[i].y1 > u[j].y2) check = false;
if(u[i].y2 < u[j].y1) check = false;
if(!check) continue;
if(f(i) != f(j)) v[f(i)] = f(j);
}
vector<int> w;
for(int i=1; i<=N; i++) w.push_back(f(i));
sort(w.begin(), w.end());
w.erase(unique(w.begin(), w.end()), w.end());
cout << w.size() << "\n";
}
}
백준 BOJ 9098번 : The Suspects
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합
N명의 학생들이 있고 M개의 그룹이 주어지며, 같은 그룹의 학생들 중 감염 의심자가 있으면 모두 감염 의심자라고 할 때, 0번 학생이 고정으로 감염 의심자라면 감염 의심자의 총 수를 구하는 문제이다.
같은 그룹에 대해 분리 집합으로 같은 부분 그래프로 만들어 주고, 마지막에 0번 노드와 같은 부분 그래프에 있는 노드의 수를 구하면 된다. (물론 0번 노드를 포함하여 count 해주어야 한다.)
#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);
while(true) {
int N, M; cin >> N >> M;
if(N == 0 && M == 0) break;
v.clear();
v.resize(N);
for(int i=0; i<N; i++) v[i] = i;
while(M--) {
int K; cin >> K;
vector<int> u(K);
for(int i=0; i<K; i++) cin >> u[i];
for(int i=0; i<K; i++)
if(f(u[i]) != f(u[0])) v[f(u[i])] = f(u[0]);
}
int ans = 0;
for(int i=0; i<N; i++)
if(f(i) == f(0)) ans++;
cout << ans << "\n";
}
}
백준 BOJ 15789번 : CTP 왕국은 한솔 왕국을 이길 수 있을까?
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합
여러 국가들의 동맹 관계가 주어지고, 그들 중 CTP 왕국의 번호와 한솔 왕국의 번호가 주어지며, 가능한 추가 동맹의 횟수가 주어질 때 한솔 왕국을 제외한 동맹들과 동맹을 맺어 만들 수 있는 최대 동맹국의 크기를 구하는 문제이다.
먼저 동맹의 크기를 구해야 하므로 u 벡터에 그룹의 크기를 저장하도록 한다.
K번의 반복문마다 CTP 왕국이나 한솔 왕국과 같은 동맹이 아니면서 가장 큰 동맹의 크기를 찾고, 그 동맹을 찾아서 같은 부분 그래프로 연결해버리면 된다.
만약 동맹할 수 있는 국가가 없으면 continue 해주면 된다.
#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 N, M; cin >> N >> M;
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
vector<int> u(N+1, 1);
while(M--) {
int a, b; cin >> a >> b;
if(f(a) != f(b)) {
u[f(b)] += u[f(a)];
v[f(a)] = f(b);
}
}
int x, y, K; cin >> x >> y >> K;
while(K--) {
int Max = 0;
for(int i=1; i<=N; i++) {
if(f(i) == f(x) || f(i) == f(y)) continue;
Max = max(Max, u[f(i)]);
}
if(Max == 0) continue;
for(int i=1; i<=N; i++) {
if(f(i) == f(x) || f(i) == f(y)) continue;
if(u[f(i)] == Max) {
u[f(i)] += u[f(x)];
v[f(x)] = f(i);
break;
}
}
}
cout << u[f(x)] << "\n";
}
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 백준 BOJ 구현, 시뮬레이션 문제 위주 풀이 모음 220811 (0) | 2022.08.11 |
|---|---|
| 백준 BOJ 풀이 : Gold 난이도 DP 문제들 220810 (0) | 2022.08.10 |
| 백준 BOJ 문제 풀이 모음 220804 (0) | 2022.08.04 |
| 백준 BOJ 브론즈 ~ 실버 기하 문제들 풀이 모음 등 220803 (0) | 2022.08.03 |
| 백준 BOJ 기하, 에라토스테네스의 체, DP 등등.. 220802 (0) | 2022.08.02 |