안녕하세요, 이번 포스팅에서는 C#을 이용한 코딩 테스트에서 자주 등장하는 유니온 파인드(Union-Find) 자료구조에 대해 다루어 보겠습니다.
유니온 파인드란?
유니온 파인드(또는 Disjoint Set Union, DSU)는 주로 그래프의 연결 요소를 관리하는 데 사용되는 자료구조입니다. 이 자료구조는 두 가지 주요 작업을 효율적으로 수행할 수 있도록 설계되었습니다.
- Find: 특정 원소가 속한 집합을 찾는 연산
- Union: 두 개의 집합을 합치는 연산
유니온 파인드는 주로 다음과 같은 상황에서 유용합니다:
- 그래프의 연결 성분을 찾는 문제
- 동일한 집합에 속하는 원소들을 그룹화하는 문제
문제 설명
어떤 무향 그래프가 있습니다. 그래프의 정점을 1부터 N까지 자연수로 표현하며, M개의 간선이 주어질 때, 주어진 간선으로 연결된 모든 정점의 집합을 구하세요.
입력
- 첫 번째 줄에 정점의 개수 N (1 ≤ N ≤ 105)
- 두 번째 줄에 간선의 개수 M (1 ≤ M ≤ 2 × 105)
- 다음 M줄에 에지의 양끝점을 나타내는 두 정수 a, b (1 ≤ a, b ≤ N)
출력
각 집합의 원소를 정렬하여 공백으로 구분하여 출력합니다. 각 집합의 결과는 한 줄에 출력해야 하며 집합은 오름차순으로 정렬에 출력해야 합니다.
예제 입력
5 3 1 2 2 3 4 5
예제 출력
1 2 3 4 5
유니온 파인드 알고리즘 구현
이 문제를 해결하기 위해 유니온 파인드를 구현해야 합니다. 유니온 파인드 자료구조의 기본적인 구현은 다음과 같은 방식으로 진행됩니다:
1. 자료구조 초기화
각 원소는 자기 자신을 부모로 가지도록 초기화합니다.