개요

백준1717(집합의 표현)

초기에
$n+1$개의 집합
$\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

접근 방식

1. 딱 보자마자 같은 집합에 존재하는지 파악할 수 있게하는 알고리즘인 유니온 파인드가 떠올랐다.

2. 개념만 알고 쓰는 법엔 익숙치 않아 일단 아는대로 간단하게 구현해봤는데 틀렸다.

   void AddGroup(int a, int b) {
   	parent[a]=b;
   }
   
   bool IsSameGroup(int a, int b){
   	
   	while(parent[a]!=a){
      	a=parent[a];
      }
      while(parent[b]!=b){
      	b=parent[b];
      }
   	return parent[b] == parent[a];
   }

   단순히 이런 식으로 a의 부모를 b로 정해줘서는 다른 집합끼리 합치는 게 불가능해진다.

3. 노드를 꺼낼때마다 모든 부모 노드들을 전부 루트노드로 갱신하여야한다.
   이 부분을 구현해보는게 힘들었는데 재귀함수를 이용하면 편하다.

   int GetParent(int a) {
   	if (parent[a] == a) return a;
   	else
   		return parent[a] = GetParent(parent[a]);
   }

4. 그룹에 원소를 더할 때 , 파라미터로 들어온 각 원소의 부모들을 전부 갱신하며
   루트값을 이어준다.

   void AddGroup(int a, int b) {
   
   		//b의 root의 parent를 a 로 묶어버리기
   		a = GetParent(a);
   		b = GetParent(b);
   		parent[b] = a;
   
   }
   

5. 같은 집합인지 알때도 파라미터로 들어온 두 원소의 부모들을 전부 갱신 후, 루트값을 비교해준다.

   bool IsSameGroup(int a, int b){
   		a = GetParent(a);
   		b = GetParent(b);
   
   		return b== a;
   	
   }

   전체 코드

#include<iostream>

using namespace std;

int parent[1'000'001];

int GetParent(int a) {
	if (parent[a] == a) return a;
	else
		return parent[a] = GetParent(parent[a]);
}

void AddGroup(int a, int b) {

	//b의 root의 parent를 a 로 묶어버리기
	a = GetParent(a);
	b = GetParent(b);
	parent[b] = a;

}

bool IsSameGroup(int a, int b){
	a = GetParent(a);
	b = GetParent(b);


	return b== a;
	
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
int N,M;
	cin >> N;
	for (int i = 0; i < N+1; i++) {
		parent[i] = i;
	}
	int tmpWay, tmpA, tmpB;
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> tmpWay >> tmpA >> tmpB;
		if (tmpWay) {
			if (IsSameGroup(tmpA, tmpB)) {
				cout << "yes" << "\n";
				continue;
			}
			cout << "no" << "\n";
			continue;
		}
		else {
			AddGroup(tmpA, tmpB);
		}
	}


}

생각

유니온 파인드를 어렴풋이 원리만 알고 있었는데, 구현 부분을 좀 알게된것 같다.