개념
- 핵심 두가지 연산
"Find" : 특정 원소가 속한 집합의 대표자(루트)를 찾는다.
"Union" : 두 원소가 속한 집합을 하나로 합친다.문제 풀이를 통한 개념 익히기
문제
초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
입력
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.
출력
1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)
유니온 파인드 활용하기
초기에는 각 원소가 자기 자신을 부모로 가진다.
find(1)=1, find(3)=3 을 수행한 후 부모가 다르므로 합친다. (union(1, 3) : 3의 부모를 1로 설정)
find(2)=2, find(4)=4 를 수행한 후 역시 부모가 다르므로 합친다. (union(2, 4) : 4의 부모를 2로 설정)
find(1)=1, find(4)=find(2)=2 일 때 부모가 다르므로 합친다. (union(1, 4) : 2의 부모를 1로 설정)
find(1)=1, find(2)=1 로 부모가 같으므로 같은 집합 (isSame(1,2) == true)
find(1)=1, find(0)=0 로 부모가 다르므로 다른 집합 (isSame(1,0) == false)
문제 풀어보기 (Java)
import java.io.*;
import java.util.*;
public class BOJ1717 {
private static int[] parent;
private static int find(int i){
// 부모 반환
if(parent[i] != i){
parent[i] = find(parent[i]); // 경로 압축
}
return parent[i];
}
private static void union(int a, int b){
// a와 b 합집합 연산
int ra = find(a);
int rb = find(b);
if(ra != rb){
parent[rb] = ra; // 루트 끼리 연결
// 바로 parent[b] = a; 를 하면 루트가 아닌것 끼리 적용되어 꼬일 수 있다.
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 입력 숫자 범위 (최대 N)
int M = Integer.parseInt(st.nextToken()); // 연산의 개수
parent = new int[N + 1];
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int op = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if(op == 0){
// 합집합 연산 수행
union(a, b);
}
if(op == 1){
// 포함 여부 확인
System.out.println(find(a) == find(b) ? "YES" : "NO");
}
}
}
}