집합의 수는 0을 포함한 N+1 개의 집합을 가진다.
Union-find 알고리즘을 사용하여 문제를 해결했다.
합집합 찾기라는 의미를 가진 알고리즘으로, 두 개의 노드를 집어 두 노드가 같은 그래프에 속하는지 판별한다.
- Find 는 입력한 수가 어떤 집합에 포함되어있는지 부모를 찾아준다
(재귀함수를 사용하여 부모를 찾을때까지 타고 올라간다) - Union 은 두 수 a와 b가 포함되어 있는 집합을 합쳐준다.
두 값을 비교하여 더 작은 값의 부모노드로 합쳐준다
부모가 p[1] = 1 과 p[2] = 2인 노드를 합치면
p[2] = 1로 연결되며 더 작은 1번노드를 가리키게 된다
for문으로 M개의 입력(m,a,b)을 받으며
첫번째 숫자의 m이 0이면 a,b를 union
첫번째 숫자m이 1이면 a,b를 각각 find하여 같은 집합에 포함되어있는지 확인한다.
import java.util.Scanner;
public class B1717 {
static int N,M;
static int[] parent = new int[1000001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
// 0~n+1의 수
for(int i=0; i<=N; i++){
parent[i] = i;
}
for(int i=0; i<M; i++){
int m,a,b;
m = sc.nextInt();
a = sc.nextInt();
b = sc.nextInt();
if(m==1) isSameParent(a,b);
if(m==0) union(a,b);
}
}
private static void isSameParent(int a, int b) {
a = find(a);
b = find(b);
if(a == b)
System.out.println("YES");
else
System.out.println("NO");
}
private static int find(int x){
if(x==parent[x])
return x;
else
return parent[x] = find(parent[x]);
}
private static void union(int a, int b) {
a = find(a);
b = find(b);
if(a != b){
//값을 비교하여 더 작은 값의 부모노드로 합쳐준다
// 부모가 p[1] = 1 과 p[2] = 2인 노드를 합치면
// p[2] = 1로 연결되며 더 작은 1번노드를 가리키게 된다
if(a < b) parent[b] = a;
else parent[a] = b;
}
}
}
'연습문제 > JAVA' 카테고리의 다른 글
[백준 java] 10828 - 스택 (0) | 2022.08.26 |
---|---|
[백준 java] 9935 - 문자열 폭발 (0) | 2022.08.25 |
1717-집합의 표현 (오답) (0) | 2022.08.24 |
[백준 java] 5430 - AC (0) | 2022.08.23 |
[백준 java] 3190-뱀 (0) | 2022.08.22 |