문제들
- 백준 : 집합 표현하기
- 코딩테스트 합격자들의 10장. 집합 내용 포인트!
개념
비교 하고자 하는 value 2개가 집합 상태에 있는지, 아니면 2개를 합해서 하나의 집합으로 만드는 알고리즘
find, union 함수를 작성함.
왜 트리로 표현할까?
- 개념에서 집합이라고 표현해서 이렇게 생각할 수 있지만,
알고리즘에서는 트리는 소속관계를 명시하는 자료구조이다.
그래서
어느 한 친구를 대장으로 하고, 대장값만 가지고 있다면, 서로 같은 집합인지 알 수 있다.
- 1번이 루트라고 하자.
- pV[num] = '부모의 번호'
-> 트리를 사용해서 리더 번호를 서로 저장해서 pV[2] = 1 , pV[3] = 1 이라는 정보를 가지고 있을 것이고, 이를 이용하면 보다 빠르게 너와 내가
같은 집합인지를 알 수 있어서 트리를 사용하는 것이다.
코드로 부모 어떻게 찾을 건데?
- 2개의 트리 구조이고,
-> 어쨌든, 부모를 찾기 위해서는 재귀 가 떠오른다.
Find 함수와 경로 압축.
- pV[2] = 1 , pV[3] = 1 는 오른쪽 그림을 표현한것이지만,
- 기본 트리방식이라고 한다면, root를 생각해낼 수 있다. (왼쪽 그림)
: pV[1] = 1 , pV[2] = 1, pV[3] = 2, pV[4] = 3;
생각해보기
- 그렇다면 집합에 새로운 친구가 추가될 때 마다. 1번 루트 아래로 주렁주렁 매달려서 높이가 높아질 것이다.
-> 부모 찾을 때 재귀로 하자고 했는데, 트리 높이가 길어지므로 비효율적.
(pV[1] = 1 , pV[2] = 1, pV[3] = 2, pV[4] = 3; // 부모값을 가지고 또 재귀를 해서 1번 값이 루트값이네... 그런데 재귀가 많다.)
경로 압축
: 재귀를 할 때마다 그냥 pV[num] = Find(pV[num]) 대입해버리기
(pV[1] = 1 , pV[2] = 1, pV[3] = 1, pV[4] = 1;)
이렇게 해버리면 매번 재귀해서 1번을 찾을 필요 없다.
동시에 그냥 부모 찾을때 반환해야 하므로, 아래의 코드처럼 작성함.
return pV[num] = Find(pv[num]);
- 코드
: 내가 그냥 루트값이라고 한다면, 굳이 재귀할 필요가 없다!
초기화
Find 함수에서 내가 루트인지를 작성하면서 초기화를 어떻게 할까? 생각할 수 있따.
나의 정점이 루트값이라고 한다면, 그냥 내번호를 반환하면 된다.
따라서 모든 정점은 자신의 번호로 초기화 하자.
- 만약에 부모가 생겨서 변경된다면, Union에서 해줄거다!
Union 함수
- "왜 트리로 표현할까?" 문단 에서 pV에 루트 노드값을 모두 저장해놓자고 했다. 이에 대한 정책을 알아보자.
정책
- 어떤 친구를 부모노드로 지정할까??
: 값이 작은 값을 부모노드로 지정함.
- 그런데 "Find 함수와 경로 압축." 문단에서 부모노드값을 가지고 와서 저장하기로 했으므로, 이를 활용하기 위해서 Find 함수를 호출하고 있는 것을 확인할 수 있다.
최종 코드 : 백준 집합 표현
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> parentV;
int Find(int a)
{
// 1(root) - 2 - 3 으로 연결된 집합이 있고,
// 맨 처음에 자기 자신이면 아직 union된게 없다거나
// 아니면 내가 root
if (parentV[a] == a)
return a;
return parentV[a] = Find(parentV[a]);
}
void Union(int a, int b)
{
// 누구를 parent로 할 것인가??
// 값이 낮은 걸로 하자.
// 그러데
// 1(root) - 2 - 3 으로 연결된 집합이 있고,
// UNION 으로 3번과 4번을 하려고 한다.
// 이 때는 4번 친구도 1번을 부모로 해야 한다.
// => 그럼 부모값을 알아야 한다.
// 이에 유념하면서 작성하자.
int parentA = Find(a);
int parentB = Find(b);
// 규칙을 내가 정하자.
// 부모가 동일하면 할 필요 없다.
// 작은 값이 부모가 되게 하자.
if (parentA < parentB)
{
parentV[b] = parentA;
}
else if (parentA > parentB)
{
parentV[a] = parentB;
}
}
int main()
{
int n, m;
cin >> n >> m;
parentV.resize(m);
for (int i = 0; i <= n; ++i)
{
parentV[i] = i;
}
// 두개의 값이 서로 집합 관계인지를
// 확인하는 문제이므로, 유니온 파인드 문제다!
for (int i = 0; i < m; ++i)
{
int a, b, c;
cin >> a >> b >> c;
if (a == 0) // 합집합하는 연산.
{
Union(b, c);
}
else
{
// 두 원소가 합인지 아닌지를 확인하는 연산.
int bb = Find(b);
int cc = Find(c);
if (bb == cc)
{
cout << "YES" << endl;
}
else
cout << "NO" << endl;
}
}
return 0;
}
🔥🔥🔥