# BOJ11724 연결 요소의 개수
https://www.acmicpc.net/problem/11724 (opens new window)
방향 없는 그래프가 주어졌을 때, 연결 요소 (connected Component)의 개수를 구한다.
# union-find
수학에서 서로소 집합 Disjoint Sets 이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다.
서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할 수 있다. union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find 연산은 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 이러한 특성 때문에 서로소 집합 자료구조는 union-find 자료구조라고 불리기도 한다.
# union
두 정점의 root를 구하여 합집합을 진행하기 위한 union 메소드이다.
private static void union(int u, int v) {
u = find(u);
v = find(v);
if (u < v) {
parent[v] = u;
} else {
parent[u] = v;
}
}
# find
두 정점의 root를 구하기 위한 find 메소드이다.
여기서는 시간 복잡도 개선을 위해서 경로 압축 기법이 사용되었다.
private static int find(int x) {
if (x == parent[x]) {
return x;
}
// 경로 압축 기법
return parent[x] = find(parent[x]);
}
# 제출 코드
위에서 작성한 union, find 메소드를 사용하여 root를 체크하고 root 노드의 목록을 저장한 parent 배열에서 중복된 값을 제외하여 개수를 출력한 뒤 마무리한다.
아래는 최종 제출 코드이다.
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class BOJ11724 {
private static int[] parent = new int[1_001];
private static int find(int x) {
if (x == parent[x]) {
return x;
}
return parent[x] = find(parent[x]);
}
private static void union(int u, int v) {
u = find(u);
v = find(v);
if (u < v) {
parent[v] = u;
} else {
parent[u] = v;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 노드의 개수 n
int m = scanner.nextInt(); // 간선의 개수 m
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
for (int i = 0; i < m; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
union(u, v);
}
Set<Integer> result = new HashSet<>();
for (int i = 1; i <= n; i++) {
result.add(find(parent[i]));
}
System.out.println(result.size());
}
}
# DFS 활용
// TODO
# BFS 활용
// TODO