boj1717-풀이
문제설명
0부터 n까지 n+1개의 독립된 집합으로 존재한다.
주어지는 연산에 따라 이 집합들을 합치고, 같은 집합에 속하는지 확인하는 문제
-> Union Find 구현문제
입력
n m
x a b (m개의 줄)
n : 원소의 수, m : 연산의 수
x : 연산종류, a, b : 합치려는 집합들의 두 원소
- x가 0일때, 주어진 두 수 a, b가 속한 집합을 합친다.
- x가 1일때, 주어진 두 수 a, b가 같은 집합에 속하는지 여부를 확인하여 YES/NO 출력
출력
1 연산에 대해
두 원소가 같은 집합에 속한 경우 YES를 출력
그렇지 않은 경우 NO를 출력예시 및 설명
입력 (그림을 잘못그려서 원소갯수를 하나 늘렸다.. 7->8)
8 8 0 1 3 1 1 7 0 6 7 1 7 1 0 3 7 0 2 4 0 1 1 1 1 1출력
NO NO YES - 각각 독립된 집합으로 존재
// 상태 rank[8] = {1, 1, 1, 1, 1, 1, 1, 1} parent[8] = {0, 1, 2, 3, 4, 5, 6, 7}
- 1과 3이 속한 집합을 합침 (union-by-rank에 의해 1의 rank 증가)
- 1과 7이 같은 집합이 아님 -> NO
// 코드 Union(1, 3) cout << (Find(1) == Find(7) ? "YES" : "NO") // 상태 rank[8] = {1, 2, 1, 1, 1, 1, 1, 1} parent[8] = {0, 1, 2, 1, 4, 5, 6, 7}
- 6과 7이 속한 집합을 합침 (union-by-rank에 의해 6의 rank 증가)
- 7과 1이 같은 집합이 아님 -> NO
// 코드 Union(6, 7) cout << (Find(7) == Find(1) ? "YES" : "NO") // 상태 rank[8] = {1, 2, 1, 1, 1, 1, 2, 1} parent[8] = {0, 1, 2, 1, 4, 5, 6, 6}
- 3과 7이 속한 집합을 합침 (union-by-rank에 의해 1의 rank 증가)
3이 속한집합의 대표요소(1)와
7이 속한집합의 대표 요소(6)를 연결// 코드 Union(6, 7) // 상태 rank[8] = {1, 3, 1, 1, 1, 1, 2, 1} parent[8] = {0, 1, 2, 1, 4, 5, 1, 6}
- 2와 4가 속한 집합을 합침 (union-by-rank에 의해 2의 rank 증가)
- 1과 1이 속한 집합을 합침 (동일한 원소끼리 합치는 것은 무시)
- 1과 1이 같은 집합에 속했는지 확인 (동일한 원소는 확인할필요 없음) -> YES
// 코드 Union(2, 4) if(a != b) Union(1,1) // 상태 rank[8] = {1, 3, 1, 1, 1, 1, 2, 1} parent[8] = {0, 1, 2, 1, 4, 5, 1, 6}
풀이
이 문제에서는 딱히 풀이라 할 것은 없고,
각각의 집합으로 초기화하고, 그룹으로 묶는 과정을 보고 유니온 파인드라는 것을 빨리 알아차리면 된다.
기본 구현
아무런 최적화가 들어가지 않은 Union Find를 구현한 코드
#include <iostream>
#include <algorithm>
using namespace std;
#define NMAX 1000001
int parent[NMAX];
int n, m, x, a, b;
int Find(int p){
if(parent[p] == p) return p;
return Find(parent[p]);
}
void Union(){
a = Find(a); b = Find(b);
if(a == b) return;
parent[b] = a;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for(int i = 0; i <= n; ++i) {parent[i] = i;} // parent, rank 초기화
while(m--){
cin >> x >> a >> b;
if(x)
cout << (a == b || Find(a) == Find(b) ? "YES\n" : "NO\n");
else
Union();
}
return 0;
}
union-by-rank 추가 구현
기본구현 + union-by-rank 구현을 추가한 코드
#include <iostream>
#include <algorithm>
using namespace std;
#define NMAX 1000001
int parent[NMAX], rank_[NMAX];
int n, m, x, a, b;
int Find(int p){
if(parent[p] == p) return p;
return Find(parent[p]);
}
void Union(){
a = Find(a); b = Find(b);
if(a == b) return;
if(rank_[a] < rank_[b]) swap(a, b);
else if(rank_[a] == rank_[b]) ++rank_[a];
parent[b] = a;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for(int i = 0; i <= n; ++i) {parent[i] = i; rank_[i] = 1;} // parent, rank 초기화
while(m--){
cin >> x >> a >> b;
if(x)
cout << (a == b || Find(a) == Find(b) ? "YES\n" : "NO\n");
else
Union();
}
return 0;
}
union-by-rank + 경로압축(path compression)추가 구현, 최종코드
기본구현 + union-by-rank + path compression 을 추가한 코드
#include <iostream>
#include <algorithm>
using namespace std;
#define NMAX 1000001
int parent[NMAX], rank_[NMAX];
int n, m, x, a, b;
int Find(int p){
if(parent[p] == p) return p;
return parent[p] = Find(parent[p]);
}
void Union(){
a = Find(a); b = Find(b);
if(a == b) return;
if(rank_[a] < rank_[b]) swap(a, b);
else if(rank_[a] == rank_[b]) ++rank_[a];
parent[b] = a;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for(int i = 0; i <= n; ++i) {parent[i] = i; rank_[i] = 1;} // parent, rank 초기화
while(m--){
cin >> x >> a >> b;
if(x)
cout << (a == b || Find(a) == Find(b) ? "YES\n" : "NO\n");
else
Union();
}
return 0;
}
댓글남기기