BOJ: 집합의 표현(1717) [C++]

https://www.acmicpc.net/problem/1717

 

문제

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

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

 

입력

첫째 줄에 𝑛, 𝑚이 주어진다. 𝑚은 입력으로 주어지는 연산의 개수이다. 다음 𝑚개의 줄에는 각각의 연산이 주어진다. 합집합은 0 𝑎 𝑏의 형태로 입력이 주어진다. 이는 𝑎가 포함되어 있는 집합과, 𝑏가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 𝑎 𝑏의 형태로 입력이 주어진다. 이는 𝑎와 𝑏가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

 

출력

1로 시작하는 입력에 대해서 𝑎와 𝑏가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

 

유니온파인드 문제다.

 

유니온 파인드

서로 다른 두 원소가 같은 집합에 속해 있는지 판별하는 알고리즘. 복잡도는 O(a(N)). O(1)에 가까움

두 원소가 같은 집합에 속해 있다면, 둘을 연결했을 때 사이클 발생. 다른 말로 하면 속한 그래프의 루트 정점이 같으면 같은 집합에 속해 있고 그렇지 않으면 아니다.

1) Find 연산: 각 원소가 속한 집합을 판별

트리를 연결하면서 각 정점의 부모를 표시. 시간복잡도를 줄이기 위해 Find 연산을 하면서 각 정점의 부모를 루트 정점으로 설정하여 그래프를 압축함

int findParent(int node) {
	if (parent[node] < 0) {
		return node;
	}
	return parent[node] = findParent(parent[node]);
}

 

2) Union 연산: 서로 다른 집합에 속한 두 원소를 같은 집합에 속하도록 합침

find 연산을 통해 다른 집합인 것이 확인된 정점들을 union.

이때 두 집합 중 원래 그래프 크기가 더 큰 것이 새 집합의 루트가 되는 것이 더 효율적이므로 각 집합의 크기 저장 필요

각 정점을 -1로 초기화하고, 각 정점의 부모를 탐색하며 값 변경.

저장된 값이 음수 - 해당 정점이 루트 정점. 저장된 값의 절댓값이 집합의 크기

저장된 값이 양수 - 저장된 값을 따라가면 해당 정점이 속한 집합의 루트를 알 수 있음

void unionInput(int x, int y) {
	int xp = findParent(x);
	int yp = findParent(y);
	if (xp == yp) return; //이미 같은 집합에 속해 있다면 return
	if (parent[xp] < parent[yp]) {
		swap(xp, yp);
	}
	//집합 크기가 더 큰 쪽에다 합침
	parent[yp] += parent[xp];
	//새로운 루트 yp
	parent[xp] = yp;
}

 

전체 코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> parent;

int findParent(int node) {
	if (parent[node] < 0) {
		return node;
	}
	return parent[node] = findParent(parent[node]);
}

void unionInput(int x, int y) {
	int xp = findParent(x);
	int yp = findParent(y);
	if (xp == yp) return; //이미 같은 집합에 속해 있다면 return
	if (parent[xp] < parent[yp]) {
		swap(xp, yp);
	}
	//집합 크기가 더 큰 쪽에다 합침
	parent[yp] += parent[xp];
	//새로운 루트 yp
	parent[xp] = yp;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m, cmd, a, b;
	cin >> n >> m;
	parent.assign(n + 1, -1);
	while (m--) {
		cin >> cmd >> a >> b;
		if (cmd==0) { //합집합
			unionInput(a, b);
		}
		else { //find
			if (findParent(a) == findParent(b)) {
				cout << "YES\n";
			}
			else {
				cout << "NO\n";
			}
		}
	}
	return 0;
}