[C++] 백준 1717: 집합의 표현

Cyan·2024년 2월 26일
0

코딩 테스트

목록 보기
113/166

백준 1717: 집합의 표현

문제 요약

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

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

문제 분류

  • 자료 구조
  • 분리 집합

문제 풀이

집합을 표현하는 유니온 파인드로 푼 문제이다. 현재 노드를 n이라고 하면, 부모 노드를 p[n]으로 표현하였다. 또한 최상위 부모노드, 즉 루트노드에는 해당 집합의 크기가 절댓값인 음수로 넣어주어서 p[n]0미만인 경우에 n번 노드가 루트 노드임을 명시했다.

find() 연산 시에도 현재 노드에서 부모 노드로 올라가는데, 올라가면서 방문하는 노드들도 루트로 연결하여 find() 연산의 최적화를 꾀했다.

merge()의 경우 두 집합이 같은 집합인지 확인한 후에 병합해주었다. 병합 시에도 루트 노드로 삼은 노드의 값에 집합의 크기를 누적해주었다. 집합의 크기는 이 문제에서 이용하지 않았지만, 해당 기법이 있다는 것만 참고하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int p[1000001];

int find(int n) {
	if (p[n] < 0) return n;
	p[n] = find(p[n]);
	return p[n];
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	p[a] += p[b];
	p[b] = a;
}

int main()
{
	int n, m, in, a, b;
	scanf("%d%d", &n, &m);
	memset(p, -1, sizeof(int)*(n + 1));

	while (m--) {
		scanf("%d%d%d", &in, &a, &b);
		if (in) {
			if (find(a) == find(b)) printf("YES\n");
			else printf("NO\n");
		}
		else merge(a, b);
	}
	return 0;
}

0개의 댓글