[C++] 친구인가?(Union&Find) ⭐

Union-Find, 또는 Disjoint-Set,는 그래프 이론과 컴퓨터 과학에서 사용되는 자료 구조입니다. 이 자료 구조는 여러 원소 집합을 관리하고 원소 간의 관계를 효과적으로 조사할 수 있도록 도와줍니다. 주로 연결 요소를 관리하거나 등가성 판별을 위해 사용됩니다.

 

Union(x, y): 두 집합을 하나로 합칩니다. 즉, 원소 x가 속한 집합과 원소 y가 속한 집합을 합쳐서 하나의 집합으로 만듭니다.

Find(x): 원소 x가 속한 집합을 찾아서 대표 원소(또는 부모 원소)를 반환합니다. 이 연산을 통해 원소 간의 관계를 확인할 수 있으며, 두 원소가 동일한 집합에 속하는지 확인할 수 있습니다.

 

📄문제

오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학생들의 친구관계를 알고 싶다.

모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각각 두 명의 학생은 친구 관계가 번호로 표현된 숫자쌍이 주어진다.

만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다.
그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다.
학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램을 작성하세요. 

두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다.

 

⬇️ 입력

첫 번째 줄에 반 학생수인 자연수 N(1<=N<=1,000)과 숫자쌍의 개수인 M(1<=M<=3,000)이주어지고, 다음 M개의 줄에 걸쳐 숫자쌍이 주어진다.
마지막 줄에는 두 학생이 친구인지 확인하는 숫자쌍이 주어진다.

9 7 1 2 2 3 3 4 4 5 6 7 7 8 8 9 3 8

 

⬆️ 출력

첫 번째 줄에 “YES"또는 "NO"를 출력한다.

NO

 

📝 풀이

#include <iostream>

int arr[1001];

// 현재 가르키는 n번이 어느 조합에 속해있는지 리턴
int Find(int n)
{
	// 인덱스 번호와 n이 같다면 자기 자신이 루트 노드
	if (arr[n] == n)
		return n;
	else
		// arr[n] != n이라면, n은 어느 조합에 속해있는 상태이기에 루트를 찾으러 재귀 호출
		// arr[n]에 루트 노드의 값을 넣어 점프할 수 있도록 최적화
		return arr[n] = Find(arr[n]); 
}

// a가 속한 조합을 b의 조합으로 변경
void Union(int a, int b)
{
	a = Find(a);
	b = Find(b);

	if (a != b)
		arr[a] = b;
}

int main()
{
	int N, M;
	scanf_s("%d %d", &N, &M);

	for (int i = 1; i <= N; ++i)
		arr[i] = i;

	int a, b;
	for (int i = 0; i < M; ++i)
	{
		scanf_s("%d %d", &a, &b);

		// 입력과 동시에 병합
		Union(a, b);
	}

	scanf_s("%d %d", &a, &b);

	// a 와 b의 조합을 확인
	a = Find(a);
	b = Find(b);

	if (a == b)
		printf("YES");
	else
		printf("NO");
}

• Union, Find 함수를 구현하여 문제를 해결합니다.
• 입력과 동시에 Union을 통해 서로가 같은 조합에 속하도록합니다.
• 마지막에 Find에서 a와 b가 속한 조합을 찾을 때, 서로 같다면 YES를 출력합니다.