서로소 집합
1. 문제 접근 방법 및 아이디어
이 문제는 여러 개의 원소가 있을 때, 이들을 합치거나 같은 그룹에 속해 있는지 확인하는 과정을 효율적으로 처리하는 것이 핵심입니다.
- 독립된 원소 생성
- 처음에는 모든 숫자가 각각 자기 자신만을 원소로 갖는 집합이 됩니다.
- 연산 식별
0 a b: 두 원소 a와 b가 포함된 집합을 하나로 합칩니다.1 a b: 두 원소 a와 b가 같은 집합에 있는지 확인하고 결과를 출력합니다.
- 대표자(Root) 개념 도입
- 각 집합을 트리 구조로 생각하고, 그 나무 뿌리를 해당 집합의 대표자로 설정합니다.
- 두 원소의 뿌리가 같다면 같은 집합인 것입니다.
2. 필요 개념 및 알고리즘
- Union-Find
- N이 최대 10^6, M이 최대 10^5로 매우 큽니다.
- 리스트나 배열로 전체 탐색을 하며 그룹을 확인하면 시간초과가 발생합니다.
- 트리 구조를 이용해 그룹을 관리하면 매우 빠르게 합치고 찾을 수 있습니다.
- 합집합 키워드는 Union 연산
- 두 원소가 같은 집합에 포함되어 있는지를 확인은 Find 연산
- 위 두 가지 연산이 반복적으로 주어지는 서로소 집합 문제입니다.
3. 실수하는 포인트
- Union 로직
parent[bRoot] = aRoot;로 연결해야 하는데 실수로parent[bRoot] = a로 작성했습니다.
- Find 로직
- 자신이 부모 노드가 아닐 때
return parent[a] = find(parent[a])로 찾아야 하는데return parent[a] = find(a)로 작성해서 StackOverflowError를 발생시켰습니다.
- 자신이 부모 노드가 아닐 때
4. 코드 풀이
4.1 Union - Find 구현
4.1.1 변수 선언
static int N, M; // 노드의 수, 연산의 개수
static int parent[]; // 부모 노드 체크 배열
- 노드의 수 N, 부모 노드 체크 배열 선언
4.1.2 make 함수
static void make() {
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
}
- 단위 집합을 생성하는 함수 입니다.
- 처음에는 모든 숫자가 각각 자기 자신만을 원소로 갖는 집합을 생성합니다.
4.1.3 find 함수
static int find(int a) {
// 종료 조건
if (a == parent[a])
return a;
// 경로 압축
return parent[a] = find(parent[a]);
}
- 종료 조건에서 부모가 자신과 같으면 종료합니다.
- 만약 부모와 자신이 같지 않으면 자신의 부모를 탐색합니다.
- 탐색을 빨리하기 위해 경로 압축을 사용합니다.
- 자신의 가장 높은 부모를 받아서 저장합니다.
4.1.4 union 함수
static void union(int a, int b) {
int aRoot = find(a);
int bRoot = find(b);
if (aRoot == bRoot) {
return;
}
parent[bRoot] = aRoot;
}
- 두 원소 a,b의 부모 노드를 탐색합니다.
- 두 대표자가 같으면 같은 집합이기 때문에 연결하지 않습니다.
- 두 대표자가 다르면 연결합니다.
4.2 checkFind 함수
static int checkFind(int a, int b) {
int aRoot = find(a);
int bRoot = find(b);
if (aRoot == bRoot)
return 1;
else
return 0;
}
- 두 원소 a,b의 부모 노드를 탐색합니다.
- 두 대표자가 같으면 1을 반환, 다르면 0을 반환합니다.
4.3 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static int N, M; // 노드의 수, 연산의 개수
static int parent[]; // 부모 노드 체크 배열
static void make() {
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
}
static int find(int a) {
// 종료 조건
if (a == parent[a])
return a;
return parent[a] = find(parent[a]);
}
static void union(int a, int b) {
int aRoot = find(a);
int bRoot = find(b);
if (aRoot == bRoot) {
return;
}
parent[bRoot] = aRoot;
}
static int checkFind(int a, int b) {
int aRoot = find(a);
int bRoot = find(b);
if (aRoot == bRoot)
return 1;
else
return 0;
}
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine().trim());
// tc 수행
for (int tc = 1; tc <= T; tc++) {
// N, M 입력
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 부모 체크 배열 초기화
parent = new int[N + 1];
// 단위 집합 생성
make();
// 출력 내용 추가
sb.append("#" + tc + " ");
// 연산 입력
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int opt = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// 0은 Union
if (opt == 0) {
union(a, b);
}
// 1은 find 연산
else if (opt == 1) {
sb.append(checkFind(a, b));
}
} // 연산 입력 종료
sb.append("\n");
} // tc 종료
// 출력
System.out.println(sb);
}
}