백준 1717번 집합의 표현

< 백준 1717번 집합의 표현 - 마포 코딩박 >

사용한 알고리즘: Union-Find


 유니온 파인드를 구현하라는 문제였습니다. 0이 입력되면 union, 1이 입력되면 find 연산을 하면 됩니다.

문제풀이는 다음과 같습니다.

(1) (코드 7~8)
 'A[x] : x의 root' 로 설정하여 각 수들의 root 를 판별해 주었습니다.
 ( x 자기 자신이 root 인 경우 A[x]=-1 < 0 으로 설정하고, 초기 시작시 모든 점은 자기자신을 root로 합니다.)

(2) (코드 9~16)
 find 를 구현하는 함수입니다.
 A[x]<0 인 경우 해당 x 가 root 임을 활용합니다.

(3) (코드 17~23)
 union 을 구현하는 함수입니다.

	#include <iostream>
	using namespace std;
	// Union Find
	const int Max = 1000000;
	int N, M;
	// A[i]: i 의 root
	int A[Max];
	// Find 함수
	int find(int num){
	if(A[num] < 0)
	return num;
	int parent = find(A[num]);
	A[num] = parent;
	return parent;
	}
	// Union 함수
	void merge(int a, int b){
	a = find(a);
	b = find(b);
	if(a == b) return;
	A[a] = b;
	}
	int n,m,l;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; ++i) A[i] = -1;
	for (int i = 0; i < M; ++i){
	cin >> n >> m >> l;
	if(n == 0)
	merge(m,l);
	else if(n == 1){
	if(find(m) == find(l))
	cout << "YES" << '\n';
	else
	cout << "NO" << '\n';
	}
	}
	return 0;
	}

view raw BOJ 1717.cpp hosted with ❤ by GitHub