이번 글에서는 알고리즘 문제를 통해 유니온 파인드(Union-Find) 자료구조에 대해 상세히
설명하고 이를 자바로 구현해보겠습니다. 특히 코딩 테스트에서 자주 출제되는 유형의 문제를 선택하여
실제 코드를 작성해보는 과정을 진행하겠습니다.
유니온 파인드란?
유니온 파인드는 ‘서로소 집합(Disjoint Set)’을 관리하기 위한 자료 구조로, 주로 그래프에서 연결 요소를
찾거나 특정 두 원소가 같은 집합에 속하는지를 판단하는 데 유용합니다. 이 자료구조의 주요 연산은 두 가지입니다.
- Find: 어떤 원소가 속한 집합을 찾는 연산입니다.
- Union: 두 개의 집합을 합치는 연산입니다.
알고리즘 문제 설명
지금부터 해결해볼 문제는 연결 요소의 개수 구하기입니다. 주어진 n개의
정점과 m개의 간선이 있을 때, 연결 요소의 개수를 구하는 문제입니다. 연결 요소란,
그래프에서 서로 연결된 정점들의 집합을 의미합니다.
예를 들어, 아래와 같은 그래프를 생각해 봅시다. 만약 정점이 5개이고 간선이 아래와 같다면,
1 - 2
| |
3 - 4
5
여기서 연결 요소는 {1, 2, 3, 4}와 {5}로 두 개 있습니다.
문제 정의
주어진 정점 n과 간선의 리스트 edges가 있을 때, 연결 요소의 개수를 출력하시오.
입력:
n = 5
edges = [[1, 2], [1, 3], [2, 4]]
출력: 2
문제 풀이 접근
유니온 파인드를 사용하여 이 문제를 해결할 수 있습니다. 각 노드를 방문하면서 해당 노드가 어떤 집합에
속하는지를 체크하고, 새로운 연결이 발견되면 이를 유니온 연산을 통해 집합에 통합합니다. 마지막에는
서로 다른 집합의 개수를 세어 연결 요소의 개수를 구할 수 있습니다.
유니온 파인드 구현
유니온 파인드를 구현하기 위해 두 가지 함수를 정의할 것입니다. 하나는 find 함수는
특정 원소의 부모를 찾아주고, 다른 하나는 union 함수는 두 원소를 연결해주는 역할을 합니다.
자바 코드 구현
public class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n + 1];
rank = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i; // 각 노드의 부모를 자기 자신으로 초기화
rank[i] = 0; // 초기 랭크는 0
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 경로 압축
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
public int countComponents(int n, int[][] edges) {
// 간선으로 유니온 연산 시행
for (int[] edge : edges) {
union(edge[0], edge[1]);
}
// 연결 요소의 개수 세기
HashSet componentRoots = new HashSet<>();
for (int i = 1; i <= n; i++) {
componentRoots.add(find(i));
}
return componentRoots.size();
}
}
메인 함수
public class Main {
public static void main(String[] args) {
UnionFind uf = new UnionFind(5);
int[][] edges = {{1, 2}, {1, 3}, {2, 4}};
int result = uf.countComponents(5, edges);
System.out.println("연결 요소의 개수: " + result); // 출력: 2
}
}
코드 분석
위 코드는 UnionFind 클래스를 만들어 유니온 파인드 알고리즘을 구현하였습니다.
생성자에서는 각 노드의 초기 값과 랭크를 설정하고, find와 union 함수를
구현했습니다. find는 경로 압축 기법을 이용해 시간 복잡도를 줄이고, union
방식으로 랭크를 사용하여 항상 균형을 유지하도록 했습니다.
결론
유니온 파인드는 그래프 문제에서 매우 유용한 자료 구조입니다. 앞서 제시한 연결 요소 개수 구하기
문제를 통해 유니온 파인드의 기초를 다질 수 있었길 바랍니다. 실제 코딩 테스트에서도 다양한 형태로
출제될 수 있으므로 이 자료구조에 대한 이해는 필수적입니다. 앞으로도 유니온 파인드를 활용한
다양한 문제를 풀어보며 더 깊이 있는 이해를 통해 실력을 쌓기를 바랍니다.